Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
46 views

Which parser has the highest reduce moves?

From what I have learned the number of reducing moves in the parsers are generally in the order LR(0)>= SLR(1) >= LALR(1). But I am unable to understand where should I place CLR(1) in this ...
0
votes
1answer
16 views

How to create a LR(k) grammar for an arbitrary k

Is there a simple procedure for constructing a grammar that is LR(k) but not LR(k-1) for any k?
4
votes
2answers
428 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
0
votes
0answers
17 views

Find equivalent LL(1) grammar

There is sample question to calculate equivalent LL(1) grammar for below grammar: $S \rightarrow S b$ $S \rightarrow S d$ $S \rightarrow c S$ $S \rightarrow c c a$ At first step, ...
0
votes
1answer
138 views

What is the Purpose of Augmented Grammar in LR parsers?

I was reading the LR() parsers from the Dragon Book where I came across these lines: To construct canonical LR(0) collection for a grammar, we define an augmented grammar and 2 functions, CLOSURE ...
0
votes
0answers
27 views

Is this correct transformation of a grammar to one without left recursion?

So the last few days I am writing a compiler for a subset of C language by given grammar for a class at university. I encountered this problem and then I realized I need to remove left-recursion in my ...
0
votes
2answers
49 views

Is this correct grammar definition of Backus-Naur form?

I've been given a grammar definition of "Simple C language" in Backus-Naur to write a compiler for a class assignment. I've been trying to implement the parser for some time now and I just can't move ...
0
votes
0answers
11 views

Detect a class of a grammar having its DSL AST

I have a grammar for some language written in some DSL for writing grammars, and this DSL implements EBNF. I have an AST for the description of a grammar in the DSL. How can I detect the minimal class ...
0
votes
1answer
34 views

Is following grammar LR(0)?

I know how to verify whether grammar is LR(0) or not. But this particular case is little tricky and hence the question. Grammar: $SL \rightarrow SL ; S \space | \space \epsilon$ $S \...
2
votes
1answer
337 views

What's wrong with this LL(1) grammar?

I am trying to build a LL(1) parse table for the following grammar: S -> L L -> L : L L -> id R R -> ( L ) R -> ( ) R -> Epsilon There are two ...
0
votes
1answer
58 views

SLR(1) Table construction, FIRST and FOLLOWS

when constructing the SLR(1) table for some grammar I need to compute the FOLLOW set for all terminals in order to decide where and when to reduce. Do I compute theme for the augmented grammar or ...
3
votes
1answer
156 views

What was Robert Floyd's algorithm for inserting brackets?

In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other ...
0
votes
1answer
42 views

Pushdown automaton from given code for parsing a while statement

I was preparing for my exam and have some questions that can possibly come on the test. There is a task to make pushdown automata from a given code: ...
0
votes
1answer
27 views

To remove all comments in a JavaScript file, do we need just a scanner or also a parser?

I was asked how to remove comments in a JavaScript program, but once I gave the regular expression solution, I was asked what if there are comments like text inside of a string: ...
14
votes
2answers
2k views

What is an IELR(1)-parser?

I try to teach myself the usage of bison. The manpage bison(1) says about bison: Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser ...
10
votes
1answer
324 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
0
votes
1answer
6k 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 : ...
0
votes
1answer
57 views

LR(1) parsing, problem with look ahead symbols

I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution. I'm trying to fill the LR(1) parsing table for the grammar ...
1
vote
1answer
334 views

Proof that the grammar is LL(2)

I am given the following grammar: $ S \rightarrow AabAba \\ A \rightarrow a | \epsilon $ and I have to prove it is LL(2). I know what LL(k) means - one can choose a production based on k characters ...
0
votes
2answers
131 views

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?

I understand the difference in the parsing tables of the above 4 parsers. I understand that CLR>LALR>SLR>LR(0) in terms of power. Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),...
2
votes
1answer
216 views

Negative lookahead in LR parsing algorithm

Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.): Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; ...
1
vote
2answers
113 views

CFG - Left factoring in recursive nested productions

I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
2
votes
1answer
33 views

How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?

In the context of languages (not grammars), I know following: $LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k)$ $LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k)...
0
votes
1answer
91 views

Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar: E->E+E*E | E-E*E E->E+E | E-E | E+E | E*E | E/E E->(E) | x I must convert it to an unambiguous one ...
0
votes
1answer
24 views

Grammar is LL(1) or not?

S -> AS | b A -> SA | a I get FIRST of S = {a,b} for S->AS and FIRST of S = {b} for S->b Hence FIRST(AS) ∩ FIRST (b) is not a disjoint This is not LL(1) But I checked this site http://smlweb.cpsc....
2
votes
1answer
75 views

Can there be a context free language that is not recognizable by a PEG?

This is related to this question. Essentially, I want to know whether my reasoning is correct. We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: ...
0
votes
1answer
40 views

CYK result de-transformation

Suppose we have a rules derived from a treebank. And in order to get a syntax tree of a given sentence we use the cyk algorithm. In order to use the cyk we should convert the rules into chomsky normal ...
0
votes
0answers
69 views

Syntax Directed Translation Scheme for Postfix to Infix Notation

I'm reading Compilers Principles, Techniques and Tools textbook and I encountered a problem from exercise 2.3 We have to construct a syntax-directed translation scheme that translates arithmetic ...
0
votes
1answer
59 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
0
votes
0answers
33 views

Converting from cfg to cnf (Chomsky normal form)

I am trying to convert this grammar from context free grammar with kleene star productions into the Chomsky normal form equivalent. I am having a hard time trying to understand how to do this, I need ...
1
vote
1answer
47 views

When and how to generate parse tree while top down parsing

I am trying to build a parser that will eventually output a 3 address code. My question is, how do I build the parser to go from parsing in a table driven top down parsing to then give me a parse ...
1
vote
1answer
46 views

What is the computational power of Parsing Expression Grammars?

Parsing Expression Grammars were introduced by Bryan Ford in Parsing Expression Grammars: A Recognition Based Syntactic Foundation.. Wikipedia says that it is an open problem to provide a Context Free ...
0
votes
1answer
43 views

How do you define and parse variables (free or bound) from user-entered strings?

I'm writing an application in which the user might enter expressions such as $\text{lim}_{i \in I} \beta(i)$ where $\beta$ is a functor. That's just an example, the expressions, which contain ...
0
votes
0answers
24 views

question about LL(1) and LR(0)

If grammar is an $LL(1)$ and does not contain any null production (i.e $V \rightarrow \epsilon$) then does that grammar necessarily be an $LR(0)$ grammar? I have tried to find counterexample for ...
1
vote
0answers
25 views

Using DPDA instead of LR parsers

If LR parsers handle only DCFLs than why we don't just use dpda to parse these languages? What are advantages of using LR parsers over DPDA? Is it that it is easy to built autonomously or something ...
4
votes
2answers
74 views

Finding the number of distinct strings in regular expression

Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from ...
2
votes
1answer
167 views

The upper bound on a Nondeterministic Finite Automata's configurations number

In "Engineering: A Compiler" 2nd ed. by Cooper and Torczon, in 2.4.1 "Nondeterministic Finite Automata" of Chapter 2, section "Equivalence of NFAs and DFAs" discusses the upper bound of a NFA's ...
0
votes
0answers
77 views

Is Python's Grammar in a known Category between CFG and CSG?

I have a high level understanding of formal languages and grammars, and I'm familiar with the four major types of grammars in Chomsky hierarchy. I was interested in knowing the classification of ...
0
votes
1answer
27 views

With a grammar, does precedence and associativity change the accepted language?

When parsing, certainly precedence and associativity effect the AST. But, do precedence and associativity alter the set of accepted sentences? In other words, can precedence and associativity be "...
0
votes
1answer
72 views

Analysis of a LALR shift-reduce conflict

I have created an extremely simple byacc grammar (ok, it's not really that simple but I simplified purposefully to be a minimal complete verifiable example): ...
1
vote
0answers
177 views

How to generate LL(1) parse table

Given the following grammar: S -> A a A -> B D B -> b B -> ε D -> d D -> ε first would be: ...
0
votes
1answer
113 views

Why is left recursion and left factoring no problem in bottom up parsing?

i am asking myself why is LR and LF no problem in bottom up parsing. I do know that we do right most derivation and so the right most non terminal is getting reduced. But why is this then a problem ...
-1
votes
1answer
183 views

What is the time complexity of LR parsers?

Bottom up parsers in worst case take O($n^3$) time, and i believe that LR parser being a bottom up parser should also take O($n^3$) time, but i read on wiki that they are able to solve problems in ...
1
vote
1answer
24 views

Calculating LL(1) grammar

I am trying to calculate the First and Follow of the following grammar S->ABC A->Aa A->aB B->Bb B-> epsilon C-> Cc C-> Epsilon I have ...
0
votes
1answer
112 views

Why ambiguous grammars are allowed for operator precedence parser?

I am aware of what is ambiguity, and why is it necessary to eliminate ambiguity in compilers in a certain context, but how can we allow ambiguity for operator precedence parser? Say I have a set of ...
0
votes
0answers
24 views

Is $LR(k) \subset SLR(k+1)$ for $k=1,2,…$? [duplicate]

I know that: Point 1: Set of languages accepted by $LR(0)$ parsers $\subset$ Set of languages accepted by $SLR(1)$ parsers Does this logic hold for higher $k$'s? That is, does following fact hold?...
0
votes
0answers
51 views

Does SLR(0), LALR(0) exists?

I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
0
votes
0answers
23 views

Proving correctness of LR parser facts

I have came across following facts while reading some compilers related text. However I did not find them in any standard reference book (mainly dragon book). Are they correct? If yes, how can we ...
0
votes
1answer
66 views

How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?

I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt: When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing ...
1
vote
1answer
53 views

is conflict possible In accepting state of LR(0)?

Consider the following grammar: Stmts -> Stmt | Stmts;Stmt Stmt -> Var =E Var ->id[E] | id E-> id | (E) in accepting state we get ...

1 2 3 4 5 8