Skip to main content

Questions tagged [parsers]

Questions about algorithms that decide whether a given string belongs to a fixed formal language.

Filter by
Sorted by
Tagged with
1 vote
1 answer
51 views

Possible mistake in a book regarding parsing and lexical analysis

I was just reading a book (Algorithms and Theory of Computation Handbook, Volume 1) and I came across the following passage : "From a practical point of view, for each grammar G = (Σ,V, S, P) ...
Aland Ameer's user avatar
1 vote
0 answers
31 views

Effect of slight modification to LL(1) parse table generation

I am experimenting with LL(1) parsers that do not use a separate lexer. I have the following grammar: S = (('<' S '>' | 'a'+) ' '?)+ The notation uses ' ...
Maximilian's user avatar
0 votes
1 answer
25 views

Discard all ambiguity from given CFG

Here is given CFG : CODE→VDECL CODE | FDECL CODE | ϵ VDECL→vtype id semi | vtype ASSIGN semicolon ASSIGN→id assign RHS RHS→EXPR | lit | char | bool EXPR→EXPR addsub EXPR | EXPR multdiv EXPR EXPR→...
bFur4list's user avatar
  • 103
2 votes
2 answers
46 views

Termination of standard encoding of CFG as PDA for words not in the language

The construction of a PDA from a CFG on wikipedia (1) is like a nice exercise for implementing a minimal-and-slow-but-functional parsing algorithm. I have a question about termination of the PDA that ...
bobismijnnaam's user avatar
1 vote
0 answers
13 views

Why would a control flow block need access to the labels associated with a higher or lower level nested control flow block?

In Engineering a Compiler (Cooper, Torczon) 3rd Edition, Chapter 5 Syntax-Driven Translation, Section 5.3.3 Translating Control-Flow Statements, the following nested control-flow grammar is presented, ...
Dean DeRosa's user avatar
1 vote
0 answers
12 views

Why must empty rules be inserted in syntax-directed translation of a control-flow grammar?

In Engineering a Compiler (Cooper, Torczon) 3rd Edition, Chapter 5 Syntax-Driven Translation, Section 5.3.3 Translating Control-Flow Statements, the following nested control-flow grammar is presented, ...
Dean DeRosa's user avatar
0 votes
1 answer
29 views

Derivation for BNF

Given a grammar for something like: h(x) or function(x) ...
User's user avatar
  • 11
0 votes
0 answers
16 views

is there a way to eliminate indirect left recursion of this grammar?

I have an indirect left recursive grammar: expr_1 := expr_1 ... ...
peterparker's user avatar
0 votes
1 answer
21 views

can left recursion be solved by adjusting the parser not the grammar?

Lets say I have a grammar I know that E -> E + T | T can be solved like this: E -> T ( + T)*. But instead can I just ...
peterparker's user avatar
0 votes
0 answers
47 views

transforming a grammar from EBNF to LL(2)

I have a grammar in EBNF and want to transform it into an LL(2) grammar. Should I omit A -> empty string ? And is there a scheme I can follow? So far I would ...
peterparker's user avatar
0 votes
2 answers
57 views

(novice to compiler design) how does a recursive descent parser decide which nonterminal to parse if there are multiple

Let's say we have a grammar S -> A | F A -> id = exp F -> id ( arglist ) ...
peterparker's user avatar
-3 votes
2 answers
38 views

Parse Tree simple example

Consider the grammar G: S ➝ A | B A ➝ aB | b | c B ➝ bA | a | ε Which of the following strings has two parse trees according to G? ba bb ab none of the choice aa ...
tmhs's user avatar
  • 97
0 votes
0 answers
23 views

Methods to tell the length of data?

What methods are there for telling a computer how long a set of data is? Here are the methods I know of: Directly telling the computer where the data begins and ends, most often with {} or (). Having ...
user avatar
0 votes
0 answers
29 views

How to use Jflex to generate a lexer properly?

I was told that making lexer from scrath is really hard and that we should use built in libraries. I used an already existing example to build my program. It worked but was full of error partially ...
Oh No's user avatar
  • 11
1 vote
0 answers
36 views

Efficiently generating valid strings from a deterministic CFG, one symbol at a time, subject to a length limit

Background I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not ...
Jerry Ding's user avatar
0 votes
1 answer
73 views

Table driven parser vs Recursive Descent parser

I am currently writing an LL(1) parser. At several places (Engineering a Compiler book, Dragon book, or this discussion), I have seen two ways to go about this, either with a table driven parser (...
Ali Ahmed's user avatar
0 votes
0 answers
62 views

Can Shared Packed Parse Forest have more than 2 families?

I am implementing Earley parser and using algorithm from Elizabeth Scott's paper "SPPF-Style Parsing From Earley Recognisers" (section 4). Author says A family of children of u will consist ...
Somnium's user avatar
  • 275
1 vote
0 answers
22 views

Number of DCFG parse tree nodes with respect to input length

I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
Petr Skocik's user avatar
1 vote
0 answers
22 views

Parsing expression grammar for a language consisting of sentences with one character added or removed anywhere

Given a parsing expression grammar for a language, is there a way to make a parsing expression grammar for a new language that consists of the valid strings from the original language, plus the ...
Alex Flint's user avatar
0 votes
0 answers
18 views

Mixfix-parser: finding associated tokens on a list

I've been trying to design an in-program programming language. Like any programming language, the input source code must go through various stages: Divide the source code into tokens. (Tokenizer) ...
Microfractal's user avatar
1 vote
0 answers
110 views

How need help to specify a grammar for arithmetic expressions

I am trying to come up with a grammar for arithmetic expressions with the following order of operations: Parentheses Factorials Exponents Functions / unary plus and minus Juxtaposition (implied ...
Chris_F's user avatar
  • 111
0 votes
0 answers
18 views

Would it be fair to describing a parser generator as a functional language?

I'm playing around with the implementation of PEGs and it struct me that the parser generator itself isn't any different than the language it's use to construct. If fact, it has all of the hallmarks ...
guidoism's user avatar
  • 131
0 votes
0 answers
24 views

Any reference implementation of PCC algorithm out there?

Currently I'm exploring LALR(1) lookahead generation algorithms to implement. I've implemented Aho and Ullman one from their textbook, but recently stumbled upon "A new analysis of LALR ...
Sunfline's user avatar
0 votes
1 answer
231 views

Is this grammar LL(1) and what is it's parsing table?

Let G be a grammar with non-terminal A, terminal a and these productions: A -> A a It is ...
Ian Rehwinkel's user avatar
0 votes
0 answers
75 views

What is the simplest parsing algorithm?

I want to learn more about parsing techniques, and to do that I'd like to start with the simplest algorithm, understand its limitations, and progress from there. From what I've seen, the best ...
user avatar
0 votes
1 answer
76 views

Can all LL(k) grammar can be recognized by LR(1)?

For context free languages, I wonder that if all LL(k) languages can be recognized by a LR(1) grammar?
xie cui's user avatar
1 vote
1 answer
49 views

Equivalence of LR(k) and LL(k′) parsers

Are there languages that can be parsed by an LR(k) parser but not by an LL(k′) parser for any k′?
Gator's user avatar
  • 11
1 vote
1 answer
28 views

Constrained precedence parsing

This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem? The setup is as follows: we are given $n$ ...
Mario Carneiro's user avatar
1 vote
1 answer
37 views

How do you convert a string representing a finite set of strings into a regulair expression without using lots of vertical bars?

Consider the following string: ...
Toothpick Anemone's user avatar
0 votes
1 answer
64 views

Parsing algorithms

I have experimented with a grammar that I could turn into a strict left-to-right finite state automaton driven algorithm (bottom up, table driven). The FSA could be complex, that's not a problem. It ...
Gunther Schadow's user avatar
2 votes
0 answers
155 views

How to write a grammar with a low-precedence unary postfix operator?

Like this person on Google Groups, I'm trying to understand how to write a grammar involving Wolfram Language's low-precedence unary & operator. The operator ...
ForceBru's user avatar
  • 121
0 votes
1 answer
66 views

How to make LR(1) grammar for sequence that cannot have more "Up" than "Down" for any given prefix?

I am working on a problem that asks me to write an LR(1) grammar that satisfies the following rules: Consider a robot arm that accepts two commands: $\triangledown$ puts an apple in the bag and $\...
Dean DeRosa's user avatar
2 votes
0 answers
143 views

Determining when a substring has a unique parse forest

Given an arbitrary (potentially ambiguous) context free grammar $G: \mathbb{G}$, and string $\alpha: \Sigma^\ast$, is there a decision procedure that returns whether appending and/or prepending ...
breandan's user avatar
0 votes
1 answer
46 views

Why is flex the best choice for handling mathematical content? (a question about approach0)

This questions is about the work A novel similarity-search method for mathematical content in LaTeX markup and its implementation. Mr. Wei Zhong uses flex lexer generator. Now, supose I find an ...
R. S.'s user avatar
  • 177
0 votes
1 answer
90 views

Why is a LALR parser the correct choice for parsing mathematical content? (a question about Approach0)

This questions is about the work A novel similarity-search method for mathematical content in LaTeX markup and its implementation. The parser used by Wei Zhong is LALR. Now, supose I have to parse a ...
R. S.'s user avatar
  • 177
0 votes
1 answer
64 views

Generating parse trees when only a recognizer is given

I am trying to understand "On the complexity of general context-free language parsing and recognition" by Walter L. Ruzzo. One of the results from the paper is about generating a parse tree ...
Rahul Gopinath's user avatar
0 votes
1 answer
77 views

Are there any updates to CYK parsing that handles epsilon rules in arbitrary nonterminals?

I am a researcher starting to work on the field of parsing and recognition of languages. As part of my background research, I am reading up on CYK. I understand that it requires the grammar to be in ...
Rahul Gopinath's user avatar
0 votes
1 answer
716 views

SLR parse table construction for left recursive grammar

I have this grammar: E -> E + T E -> T T -> T * F T -> F F -> ( E ) F -> id And this is the state diagram for it: I tried to construct a parse ...
Node.JS's user avatar
  • 151
0 votes
1 answer
121 views

Simple description of the LR(0) table generator algorithm?

I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
Gunther Schadow's user avatar
2 votes
0 answers
42 views

In GLL generated SPPF graph, how does the algorithm produce children with only one parent?

I am working through (1) "GLL Parsing" (2) "GLL parse-tree generation" and (3) "Structuring the GLL parsing algorithm for performance" by Elizabeth Scott and Adrian ...
Rahul Gopinath's user avatar
0 votes
0 answers
51 views

what are all the ways of delimiting blocks

To my knowledge, in block-structured programming languages, there are 2, maybe 3 main ways of delimiting a block. Using start and end tokens, this can be brackets or reserved words etc Using ...
StackMachine's user avatar
0 votes
1 answer
679 views

Should I lookahead in the lexer or parser?

So I have this Recursive Descent Parser which outputs a Syntax Tree for arithmetic expressions. While doing some reading, I learned that LL(1) grammars have a lookahead of 1 - I remembered using a ...
dumbPotato21's user avatar
1 vote
1 answer
159 views

Can CYK algorithm be used even if the grammar is ambiguous?

Can CYK algorithm be used for ambiguous context free grammar?
Chaitanya Kale's user avatar
0 votes
1 answer
104 views

What is bottom-up pattern matching?

On the website for the book Modern Compiler Design, it is claimed that: [The book] recognizes lexical analysis, LR parsing and BURS code generation as instances of bottom-up pattern matching and ...
hkBst's user avatar
  • 133
0 votes
1 answer
178 views

Why do we retain A->.aA,a/b in I3 stage of LALR parsing of S->AA, A->aA|B?

The question is LALR(1) parsing of the following: S->AA A->aA A->b The link to the question is on this page:https://www.javatpoint.com/lalr-1-parsing My ...
Thales's user avatar
  • 103
2 votes
1 answer
157 views

What role does an asterisk serve in Backus–Naur Normal Form?

Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form What does the asterisk (*) mean? In the example below, ...
Toothpick Anemone's user avatar
0 votes
1 answer
111 views

How can we escape the pipe character in Backus–Naur Normal Form?

Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form How can you distinguish between the pipe character as symbol in C++ or ...
Toothpick Anemone's user avatar
1 vote
1 answer
62 views

Getting something wrong while building parse table for the grammar

Task Build the Parse Table Let $\mathcal{G}$ be the following context-free grammar: $$ \begin{aligned} E &\to TE' \\ E' &\to +TE'\; |\; \epsilon \\ T &\to F T' \; \\ T' &\to *FT'|\;\;\...
bigstreet's user avatar
0 votes
0 answers
32 views

Canonicalizing Arbitrary EBNF Expressions

From what I understand, LL and LR parsing require a grammar to be in "canonical form", i.e. only productions of the form A -> b1 b2 ... bn, where ...
Federico Mantovani's user avatar
-1 votes
1 answer
254 views

Argument for an $\epsilon$ free LL(1) grammar being in LR(0)?

I am trying to understand the reason as given in this answer If an ε-free grammar is not LR(0), then there is some state with both a shift and a reduce action. Since the grammar is ε-free, that state ...
user2277550's user avatar

1
2 3 4 5
9