Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
471
questions
1
vote
4
answers
3k
views
Eliminating cycles from a grammar
I have the following grammar:
S -> Xb | Y
Y -> X | a
X -> S | c
Here the lowercase letters are terminals.
I have an algorithm to find the cycle in ...
16
votes
3
answers
2k
views
What would you get if you add parameters to context free grammars?
I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python ...
1
vote
0
answers
262
views
Is the Java 8 Grammar still a LALR(1) grammar?
As I found out here: http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html , the Java Version of 2005 (might be Java 6, I'm not sure) is a LALR(1) grammar. However, I couldn't ...
0
votes
1
answer
597
views
Neither Left nor Rightmost Derivations
Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the ...
1
vote
0
answers
43
views
Determining the set of valid next terminals when generating from a CFG
I am trying to generate random sentences from a context-free grammar. During each step, the next non-terminal to be generated is determined according to some probabilistic criteria irrelevant to this ...
9
votes
2
answers
2k
views
Correct name for a recursive descent parser that uses loops to handle left recursion?
This grammar is left recursive:
...
4
votes
0
answers
397
views
How would I build a parser generator for a context free grammar using Pushdown Automata?
I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc.
I am at the point where I have lexer generation ...
2
votes
1
answer
1k
views
Understanding context free grammars in conjunction with PDA
I have read TONS of articles about context free grammars and Pushdown Automata but I think there are things that I dont seem to understand. I am not studying computer science but I am really ...
3
votes
1
answer
3k
views
How to generate an LL(2) parse table?
The algorithms I've seen for building an LL(1) parse table involve calculating first and follow sets such that:
...
1
vote
0
answers
232
views
Converting Ambiguous Grammar G to LL(1)
So I am in the process of learning about LL(1) grammar and converting an ambiguous one into LL(1). I know how to figure out if a grammar (G) is ambiguous, however, I am having trouble converting it to ...
3
votes
1
answer
315
views
If a grammar is SLR(1) then are the LALR and SLR tables the same?
I think they are because, SLR and LALR have same number of states and, since there are no conflicts in SLR table this means all the SLR information is needed and correctly used for parsing, so all ...
1
vote
1
answer
665
views
Choosing a production with $\lambda$ in Context-Free Grammars
Given the context-free grammar
\begin{align*}
& S \rightarrow AA \\
& A \rightarrow xA \\
& A \rightarrow B \\
& B \rightarrow yB \\
& B \rightarrow \lambda
\end{align*}
What is ...
4
votes
1
answer
975
views
How to find unambiguous grammar for palindromes
I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc.
...
0
votes
0
answers
85
views
Is Kalman filter used in automata (besides cellular automata) and parsing grammars?
I am new to Kalman filter and parsers. I understand that it's suitable for prediction/estimation on the go, when you have something to measure (not only the model), and when changes always occur in ...
9
votes
2
answers
2k
views
Is there a different resolution of the "dangling else" problem other than "match closest"?
The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for ...
0
votes
0
answers
2k
views
Difference between LR parsing and Shift-Reduce parsing?
I'm learning natural language processing and I can't understand the difference between Shift-Reduce parser and LR parser.
As I've understood from Wikipedia, shift-reduce is just a name of a class of ...
5
votes
2
answers
6k
views
Bottom-Up Evaluation of Inherited Attributes
I came across $2$ translation schemes of Syntax Directed Translation (SDT) in compilers which are as follows :
Using a top-down translation scheme, we can implement any
$L$-attributed definition ...
0
votes
0
answers
281
views
Is this depth-first top-down parsing algorithm a recursive descent top-down parsing algorithm?
In Thomas Sudkamp's book, Machine and Languages, there is a depth-first top-down parsing algorithm (please see the algorithm here).
My main question is:
1) Is this algorithm a (backtracking) ...
1
vote
2
answers
751
views
Is the given grammar LL(2)?
http://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf
The book by Grune and Jacobs presents an example of a grammar that is $LL(K + 1)$ but not $LL(K)$
The example is $S -> a^kb/a^ka$
The ...
3
votes
1
answer
746
views
Eliminate left recursion from grammar
Consider the following grammar:
$$
A\to Ba|Aa|c \\
B\to Bb|Ab|d
$$
How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion?
I have tried applying the ...
0
votes
1
answer
10k
views
LL(1) parsing table construction
i have the following CFG
E -> ABC
A-> a|Cb|epsilon
B-> c|xA|epsilon
C-> y|z
and the First of the Non-Terminal :
...
2
votes
4
answers
1k
views
How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?
$\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt
$\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt
$\mid \textbf{...
4
votes
1
answer
1k
views
Bottom-Up Parser With Leftmost Derivation
I'm reading the book Parsing Techniques by Dick Grune et al. and in section 3.1.3 "Linearization of the Parse Tree" they introduce the notion of linearization:
[...] a parser can produce a list of ...
1
vote
1
answer
437
views
boolean expression syntax checking
i am trying to formulate an algorithm for syntax checking for simple boolean expression like (var1 = 10) or (var2 > 100).
evaluation part seems to be easy as i will convert infix to postfix and ...
0
votes
0
answers
139
views
Is grammar S→aaab | aab in LL(2) but not SLL(2)?
I'm trying to figure out how to create grammars which are LL(k) and not SLL(i).
Is this grammar LL(2) and not SLL(2)?
$S \to aaab \mid aab$
Where S is a starting symbol. I think it is not SLL:
...
1
vote
0
answers
92
views
Is it possible to transform this grammar into LL(1)?
This is the original grammar:
S -> ABe
A -> ab | a | ϵ
B -> b
I did try left factoring and this is what I got:
...
2
votes
3
answers
679
views
Simple question about grammar derivations
I'm learning the basics of grammars and compilers for a comparative programming languages class, but having a bit of trouble with one aspect of grammar derivation.
Here is an example of a grammar ...
4
votes
0
answers
123
views
Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?
Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing?
The ...
2
votes
1
answer
3k
views
Shunting Yard Algorithm extension and AST generation
Let me introduce you to my current project (that obviously yields the problem I face hence I post here). I am writing a so-called "compiler" for a simplistic language. I have already built a VM ...
1
vote
1
answer
102
views
Can I mix LL and LR parsing?
I want to go RD parsing with Shunting Yard for expression (for the sake of easier operator precedences and less left-recusion), is that considered no-good because nobody did that before?
6
votes
2
answers
541
views
any hope for a universal automatic parser?
Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and ...
4
votes
1
answer
538
views
Parsing CFLs (simulating PDA vs CYK algorithm)
We can simulate the PDA and parse the language with the following operations (vaguely):
Read the input symbol and top of stack - $O(1)$
Check all the transition rules (must check all for non-...
2
votes
0
answers
84
views
Correct bracketing check with rotate operation on position i
Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations:
Check whether the sequence is correctly bracketed
Rotate bracket ...
0
votes
1
answer
404
views
Context Free Grammar for Try-Catch-Finally Statement and Throw
I am currently working on a problem that is asking me to write the grammar productions for the try-catch-finally and throw C# statements. It states that "you can assume that there are nonterminals "...
3
votes
1
answer
2k
views
White-space and comment by lexical analyzer
Lexical Analyzer mostly deletes comments and white-spaces. One example where I think Lexical Analyzer might not be discarding white-spaces is in Python language, as indentation has a important role in ...
7
votes
1
answer
2k
views
Check for balanced parentheses in an expression in log-space
Given an expression (a word in the one-sided Dyck language), I want to write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in the expression. For ...
5
votes
3
answers
2k
views
Streaming parsing algorithms
A parser is a procedure which decides if an input belongs to a certain language and produces a witness in the form of a parse tree.
Let a streaming parser be a parser which for any prefix $u$ can ...
1
vote
1
answer
3k
views
Conditions for LL(1) grammar
One of the conditions for A → α | β to be LL(1) grammar states that
If β → ε in one or more steps then α doesn't derive any string beginning with a terminal in FOLLOW(A). Likewise If α → ε in one ...
1
vote
1
answer
1k
views
What is a "special sequence" in EBNF?
In Extended Backus-Naur Form (EBNF) there is one form called a "special sequence" which is surrounded by questions marks ?...?
What does this mean?
0
votes
2
answers
3k
views
Proving that a CFG generates a language [duplicate]
Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree?
What if the tree is infinite? What would then be a better way to prove that a ...
2
votes
1
answer
380
views
Does my grammar contradict LL ⊆ LR(1)?
This answer claims that $ LL \subseteq LR \left( 1 \right )$ where $LL = \bigcup_k LL(k)$.
But is this true? Is this grammar a valid counterexample?
$ S \rightarrow a | Aaa $, $ A \rightarrow \...
0
votes
1
answer
130
views
Is there any precedence for symbols for constructing parse trees? [duplicate]
I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees.
For example, the sentence: p ∧ q → r, ...
6
votes
1
answer
1k
views
What would a formal grammar for a binary file format look like?
Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive.
What would ...
0
votes
1
answer
38
views
Unsure about parse tree of PCFG
I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa.
My solution would look like
...
1
vote
1
answer
59
views
Why is particular token missing in LALR lookahead set?
I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin:
S' ::= S
S ::= L = R | R
L ::= * R | id
R ::= L
The items associated ...
1
vote
0
answers
102
views
How do merged lookahead sets help LALR parse more grammars than SLR? [closed]
From what I have searched on Google so far, the only difference between LALR(1) and SLR(1) is that LALR(1) uses states with merged lookahead sets. One source says that LALR(1) won't run into shift-...
-2
votes
1
answer
207
views
What's the step for build a SLR table for the following CFG? [closed]
(r1) E → E+T
(r2) E → T
(r3) T → T F
(r4)T →F
(r5) F → F∗
(r6) F → a
(r7) F → b
I am just doing the exercise on the workshop. I just knew how to the build the SLR state machine for this CFG. ...
1
vote
1
answer
64
views
operator precendence grammar
According to this post https://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel ...
2
votes
2
answers
187
views
Is the word problem of CFLs in NC?
Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string.
Lets say I have a ...
1
vote
0
answers
108
views
How can we avoid mistake in LL(1) parse tree?
I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...