Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
423
questions
0
votes
0
answers
14
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 ...
- 131
0
votes
0
answers
20
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 ...
- 1
0
votes
1
answer
38
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 ...
- 103
0
votes
0
answers
64
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 ...
user160778
0
votes
0
answers
39
views
Which language can be parsed recursive descent?
We consider languages over the alphabet {a,b,c}. Given a character t in the alphabet and a non-negative integer j, by t^j we mean the string consisting of exactly j occurrences of t.
Now let m be an ...
- 3
0
votes
1
answer
30
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?
- 1
1
vote
1
answer
31
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′?
- 11
1
vote
1
answer
27
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$ ...
- 531
1
vote
1
answer
36
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:
...
0
votes
1
answer
54
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 ...
- 111
2
votes
0
answers
75
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 ...
- 121
0
votes
0
answers
23
views
First Set for this grammar? Is it Indirect Left-recursive
Given the grammar (Uppercase alphabet is non-terminal, lower-case alphabet is terminal), how to find FIRST set?
A -> mB | CD
B -> CBn | epsilon
C -> pA | epsilon
D -> q
This is NOT a ...
- 1
0
votes
1
answer
50
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 $\...
2
votes
0
answers
136
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 ...
- 33
0
votes
1
answer
44
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 ...
- 137
0
votes
1
answer
78
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 ...
- 137
0
votes
1
answer
39
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 ...
- 337
0
votes
1
answer
43
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 ...
- 337
0
votes
1
answer
251
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 ...
- 101
0
votes
1
answer
77
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 &...
- 111
2
votes
0
answers
36
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 ...
- 337
0
votes
0
answers
46
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 ...
- 91
0
votes
1
answer
233
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 ...
- 115
1
vote
1
answer
68
views
Can CYK algorithm be used even if the grammar is ambiguous?
Can CYK algorithm be used for ambiguous context free grammar?
0
votes
0
answers
26
views
Circular dependency while computing Follow in Grammar
In the following grammar I want to find the follows for each non terminal.
S-> iEtSS' | a
S' -> eS | epsilon
E -> b
The issue is, when I try to find the follow for S, according to the ...
0
votes
1
answer
57
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 ...
- 133
0
votes
1
answer
57
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 ...
- 103
2
votes
1
answer
97
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, ...
0
votes
1
answer
80
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 ...
1
vote
1
answer
49
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'|\;\;\...
- 13
0
votes
0
answers
22
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 ...
-1
votes
1
answer
136
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 ...
- 275
1
vote
1
answer
28
views
Edit distance into a DCFL
I would like to generate helpful parser errors, telling the user how to fix their program.
Specifically I have a deterministic context-free language $L$, given in the form of an $LR(1)$ grammar. I ...
- 709
1
vote
1
answer
1k
views
How is the lookahead for an LR(1) automaton computed?
I'm reading Douglas Thain's book called "Introduction to Compilers and Language Design" and I've come across the following grammar:
, with the following LR(1) automaton:
, and I am not ...
- 135
-1
votes
1
answer
199
views
What is the time complexity of SLR and LALR parsers?
What is the difference between time complexity of SLR(k) and SLR(1)? and also what about LALR(k) and LALR(1)?
How can I calculate time complexity of parsers? I think time complexity of LR(k) is O(n) ...
0
votes
2
answers
409
views
LR(1) grammar that can not be transformed an LL(1) grammar
Looking for an example of a LR(1) grammar that can not be turned into an LL(1) grammar that parsers the same language.
- 237
1
vote
1
answer
105
views
Strategy to designing grammar for a LR(1) parser
Is it better to think about tokens from right to left and perform right factoring on grammar for an LR(1) parser? As apposed to thinking about tokens left to right and doing left factoring on grammar ...
- 237
1
vote
0
answers
173
views
Relation between left derivations, right derivations and number of parse trees?
I saw this question on a test-prep site
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
...
- 275
1
vote
1
answer
51
views
How is the lookahead set computed for the Earley algorithm?
I read the dissertation [1] and the paper [2], but I'm not sure how to compute $H_{k}$.
$H_{k}$ is defined as:
$$H_{k}(\gamma) = \{ \alpha | \alpha \text{ is terminal,} |\alpha| = k \text{ and } \...
- 111
3
votes
2
answers
292
views
LALR(1) grammar for simple math parser
I am trying to write a simple parser for a small calculator project, that should be able to parse e.g. the following inputs:
...
- 33
1
vote
2
answers
2k
views
Proving the grammar S → SS+ | SS∗ | a is unambiguous
Consider the context-free grammar G = ({a, +, ∗}, {S}, {S → SS+ | SS∗ | a}, {S}) and consider the string aa+a* generated by this grammar.
Is this grammar unambiguous?
I have browsed the Internet and I ...
- 127
-1
votes
1
answer
105
views
Lexical analysis on a series of tokens given regexes
I am to parse through a series of strings with a given token list. I was wondering if my lexical analysis is correct.
...
- 1
0
votes
0
answers
9
views
Text macros(replacements) based on pre-defined rules
I'm writing a web app that requires a component that let's the user input a piece of text thats automatically formatted based on something the client calls "macros". These macros have a very ...
0
votes
2
answers
135
views
How to detect if a CFG can cause the parser ends up looping forever?
For example, the following grammar will never stop deriving a complete sentence:
S -> A b
A -> a A
Some other CFGs can derive a complete sentence, but it ...
- 111
0
votes
1
answer
19
views
Computing Earley Parsing Steps
I am trying to understand Earley parsing algorithm using an example. The grammar I use produces all the palindromes over $\Sigma=\{a,b,c\}$:
\begin{align*}
Z & \to S\\
S & \to a\,|\,b\,|\,c\,|\...
- 163
0
votes
1
answer
329
views
Reduce-reduce conflict in SLR vs LALR
I was wondering if I could say any of the following is true.
Given a grammar $G$,
If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$.
...
3
votes
1
answer
322
views
Why can't a LR(0) parser have GOTO and Reduce Items in the same canonical set?
I am talking in reference to this question from this compiler test. I think it is actually true that a GOTO and REDUCE can't be present in the same set, but am having a hard time coming up with an ...
- 35
1
vote
0
answers
64
views
How does one parse a string into an AST (Abstract Syntax Tree) directly instead of to a CST (Concrete Syntax Tree)?
I wanted to parse strings to AST data structures instead of CSTs - which introduce a lot of intermediate nodes like terminal that might not be needed. I am not sure if one first creates a CST and then ...
- 2,960
0
votes
1
answer
311
views
How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?
As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
- 9,461
2
votes
1
answer
338
views
How does LALR(1) parser behave compared to LR(1) paser?
In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads:
"The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... ...
- 9,461