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
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 ...
James Smith's user avatar
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 ...
Aivar's user avatar
  • 285
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 ...
Niklas Wünsche's user avatar
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 ...
Synex's user avatar
  • 115
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 ...
user7954416's user avatar
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: ...
user71015's user avatar
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 ...
jchitel's user avatar
  • 151
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 ...
Asperger's user avatar
  • 123
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: ...
Max Heiber's user avatar
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 ...
ShadowViper's user avatar
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 ...
Gopick's user avatar
  • 31
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 ...
Soupy's user avatar
  • 113
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. ...
adamrob9's user avatar
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 ...
kate's user avatar
  • 327
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 ...
Gro-Tsen's user avatar
  • 393
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 ...
Amir's user avatar
  • 101
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 ...
Garrick's user avatar
  • 462
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) ...
kate's user avatar
  • 327
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 ...
Garrick's user avatar
  • 462
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 ...
primitzisgate7's user avatar
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 : ...
user62516's user avatar
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{...
Akhil Nadh PC's user avatar
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 ...
cadaniluk's user avatar
  • 201
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 ...
deb's user avatar
  • 9
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: ...
Milano's user avatar
  • 339
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: ...
Asnira's user avatar
  • 111
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 ...
Dave's user avatar
  • 495
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 ...
Liisi's user avatar
  • 141
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 ...
TDk's user avatar
  • 133
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?
Steve Fan's user avatar
  • 121
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 ...
reuns's user avatar
  • 170
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-...
aste123's user avatar
  • 445
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 ...
Ondra Hrubý's user avatar
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 "...
JanVanLeiden's user avatar
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 ...
Mayank Jain's user avatar
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 ...
kunteynir's user avatar
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 ...
Ulrik Rasmussen's user avatar
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 ...
jblixr's user avatar
  • 111
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?
Tyler Durden's user avatar
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 ...
ethane's user avatar
  • 264
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 \...
Daniel's user avatar
  • 23
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, ...
ethane's user avatar
  • 264
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 ...
Matheus Moreira's user avatar
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 ...
Kendel Ventonda's user avatar
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 ...
npCompleteNoob's user avatar
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-...
npCompleteNoob's user avatar
-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. ...
pocky0719's user avatar
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 ...
whd's user avatar
  • 121
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 ...
Smarty77's user avatar
  • 123
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 ...
Pavan's user avatar
  • 111

1
4 5
6
7 8
10