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
14 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
0answers
18 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 ...
0
votes
0answers
20 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
55 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 ...
0
votes
1answer
21 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
1answer
42 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
1answer
24 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
0answers
46 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
16 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
44 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
1answer
20 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
38 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
33 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
70 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
22 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
0answers
21 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
31 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
1answer
25 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),...
0
votes
0answers
22 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
31 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 ...
0
votes
1answer
33 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 ...
1
vote
1answer
41 views

Wikipedia says this grammar is LR(0), but Grammophone says it is not; is it?

E -> E * B . E -> E + B . E -> B . B -> 0 . B -> 1 . I am confused because Wikipedia cites this grammar as an example of an LR(0) grammar ...
0
votes
1answer
53 views

Is there a LL(K) Grammar which is not LALR(K) Grammar?

It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And ...
0
votes
1answer
57 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 ...
1
vote
2answers
132 views

What is the use of First() and Follow() in compiler design?

I am completely aware of how to calculate first and follow, my professor has taught me that well , but he had not explained what is the need of First() and Follow(), so any explanation why we need ...
3
votes
1answer
78 views

Can Earley parser work in parallel?

Since Earley parser finds all possible application variants for a token, can it parse text in parallel, unlike the usual parser like stack-based, etc. You just need to modify the start of each ...
1
vote
1answer
39 views

Unambiguousness and determinism of CFGs for them to be LR

I came across this statement: Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts. I was ...
1
vote
0answers
25 views

CYK algorithm - how to handle unknown terminals given in a sentence to parse?

There is a given treebank which we derive the Probabilistic context free grammar. I wonder how do one handles with a given sentence which includes terminals that don't exist in the derived rules? Is ...
2
votes
1answer
75 views

Connection between non determinism and LL(1) conflicts

I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it. As per my understanding non deterministic context free grammar is a context free grammar ...
0
votes
0answers
77 views

Understanding handle, viable prefix and valid item in the context of LR(0) and LR(1) items

Dragon book gives definition of handle, viable prefix and valid item at various different places. I am trying to understand these definitions in each other's context. Various definitions given are as ...
1
vote
1answer
119 views

When will SLR(1) parser fail but CLR(1) will not

Dragon book says following about where SLR(1) parser can fail but CLR(1) wont: Recall that in the SLR method, state $i$ calls for reduction by $A→α$ if the set of items $I_i$ contains item $[A→α.]$...
1
vote
1answer
60 views

context-free grammar for comma-separated list with comments

I'm trying to write a context-free grammar for a comma-separated list of statements with comments. It is trivial if the comma appears at the end of a statement. It is trivial if the comment is ...
2
votes
1answer
73 views

In what sense a type of parser is less power than the other?

I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers. I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the ...
0
votes
0answers
17 views

Connection of relation between valid item and viable prefix with canonical collection

I was trying to understand connection between different concepts of parsers and how those are followed in actual parsing steps. I came across following statement while reading LR parsers: An item ...
0
votes
0answers
50 views

Creating a grammar for a a language for instructions, with repititions

I have a language that consists of instructions for movement on a 2D-plane. You start at coordinate [0,0] The instructions DOWN 1 UP 10 LEFT 5 RIGHT 1 means you ...
0
votes
0answers
37 views

Understanding the rules of parsing table construction

I'm studying top-down parsing, especially LL(1) parsing. However, I cannot understand what is the meaning of rules. Example grammer is like this S → ( S ) S | $\epsilon$ How can I derive like ...
2
votes
2answers
43 views

Why can we (apparently) implement CFG parsers only using (N)DFAs?

I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be nested. For parsing those files I ...
1
vote
1answer
42 views

Check grammar for LL(1)?

If I have to check a Left Recursive grammer for LL(1) then should I check it after removing left recursion? For example:- S-> (L)|a L->L.S|S If I check after removing Left Recursion then the above ...
1
vote
1answer
80 views

How to find First in a left recursive grammar?

One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed. If a grammar is left-recursive, then the set of ...
1
vote
1answer
45 views

Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous. I couldn't make up my mind on this statement. How can a grammar which is both ...
0
votes
0answers
143 views

The rightmost derivation is possible with the same rule of leftmost derivation

Can someone please help me in understanding the statement. What does it exactly mean? What I think it means is that: the derivation produces by the leftmost derivation is also possible with rightmost ...
1
vote
1answer
39 views

Is this a proper LL(1) Grammar?

Please take this question with a grain of salt. I'm trying to write a very simple layout engine and wanted to formally create a grammar to parse the input. I stayed up all night researching LL(k) ...
3
votes
1answer
141 views

Bottom up chart parser adding active arc step

I am following Bottom up chart parsing algorithm from Natural Language Understanding book by James Allen. It is I couldn't understand the 3rd step. I thought that when active arc is added the dot ...
3
votes
1answer
49 views

SLR parse table and unambiguity

If it is possible to construct an SLR parse table with no conflicts for a particular grammar does that mean that the grammar is unambiguous? I think that since we have constructed the parse table ...
1
vote
0answers
16 views

State of the art of parser handling of offset errors

Say you are parsing a complicated binary file but there is 1 extra byte inserted somewhere. This could completely mess up the entire parse, but if you just looked ahead one token you would see the ...
0
votes
0answers
41 views

Get grammar from his LALR(1) parsing table

I have a problem with this exercise. This is the LALR(1) parsing table for the grammar G. How can i get the productions of G? Thanks :)
0
votes
1answer
47 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 ...
1
vote
1answer
50 views

Is the following Grammar LL(1)

I was given the following grammar $S \rightarrow S ( S ) S\mid \epsilon$ First I was asked to eliminate left recursion, yielding me the following : $S \rightarrow S' $ $S' \rightarrow (S)...
1
vote
0answers
18 views

what are the limitations of definite clause grammars?

Definite clause grammars have been around for a long time but there are not the answer to every parsing problem or we would not need to invent new formalisms. Are there any languages they cannot ...
0
votes
1answer
26 views

How to solve the following left recursion?

A common left recursion: A -> Aa | B can be solve by transforming it into: A -> BA' A' -> aA' | E However, I ...