Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [parsers]

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

1
vote
1answer
11 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
votes
0answers
35 views

I want learn more about parsing [on hold]

I want to learn more about parsing and I'm looking for a good resource to understand LL parser because I want to implement an LL parser in C, I looked for relevant material but I don't understand how ...
1
vote
1answer
33 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 ...
1
vote
1answer
30 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
12 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
43 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
31 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
29 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
24 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
30 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
28 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
90 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
32 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
132 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 ...
2
votes
1answer
29 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
14 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
36 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
33 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
43 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)...
0
votes
0answers
14 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
22 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 ...
0
votes
1answer
35 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
vote
0answers
18 views

Is there any difference in the expressiveness of boolean grammars versus definite clause grammars?

Definite clause grammars have been around a long time and are included in logic languages such as Prolog. They can be translated into (are just syntactic sugar for) Prolog programs and are therefore ...
1
vote
0answers
68 views

Do SLR(1) parsers have lookahead?

The SLR(1) parses AFAIK does not have any lookahead with it then why do we write it as SLR(1) and not as SLR(0). The thing about parsers which I read online taught me that if it's LR(K) then K ...
2
votes
1answer
300 views

Prove that every CFL is decidable in O(n) space

this question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was: Prove that every context free language $A$ is in $\mathrm{SPACE}...
2
votes
0answers
40 views

What strategies exist for handling/resolving ambiguity in parsers?

I define a parser as a context-free grammar with semantic actions for each production. It is not defined in what order the semantic actions run, just that the semantic actions of the non-terminals in ...
2
votes
1answer
52 views

Leo's deterministic reduction for Earley Parsing

I am trying to build an Earley parser using the Wikipedia pesudocode as a base, with Aycock's fix for epsilon rules as follows: ...
2
votes
1answer
50 views

Parser theory: How to systematically compute FOLLOW sets?

Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have ...
0
votes
1answer
39 views

First Sets: If $A \to Ad\ |\ c$, what is $First(A)$?

Suppose that we have a grammar with the following rules: $$S \to Aa\ |\ b\ |\ \varepsilon\\ A \to Ad\ |\ c$$ From looking at it I already know that $First(S) = \{b, \varepsilon, c\}$. My question is:...
0
votes
1answer
26 views

LL(1) and LR(0) Grammars

The value in the parenthesis of language expressions signify how many next symbols are needed to make a decision. For example, without reading a symbol from the input, we cannot decide in LL(1) ...
0
votes
1answer
104 views

LR parsers and ambiguous and non deterministic grammars

Dragon book says: An ambiguous grammar can never be LR. And then immediately further it says: For example, consider the dangling-else grammar: $\begin{align} stmt \rightarrow & \textbf{...
1
vote
0answers
15 views

Clear definitions of various terms related to top down parsers and classification of the same

I am trying to clearly define various terms related to top down parser "so that I can relate them and come up with clear classification". Now this efforts might seem unnecessary as the terms I am ...
0
votes
1answer
129 views

Handling epsilon productions in recursive descent parsing

I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions: ...
0
votes
1answer
56 views

Is this a correct grammar for untyped lambda calculus?

I am trying to write a recursive-descent parser for untyped lambda calculus. While researching the way of formulating the grammar, I managed to put together something like this: ...
1
vote
0answers
114 views

How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.(\| is the escape character, since | is a special character in grammar's pattern). ...
0
votes
1answer
105 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 ...
1
vote
2answers
43 views

Why can't exhaustive search parsing stop after |w| + 1 derivations?

If my grammar does not have productions of the form $A\rightarrow\lambda$ and $A\rightarrow B$ for some variables $A$ and $B$ then I know that each step in the derivation must involve an increase in ...
1
vote
1answer
14 views

Choosing correct action in bottom up parsing

Using grammar: $ S \to aABe \\ A \to bcA \mid c \\ B \to b $ to bottom parse a string $abcccde$, the course of action would be: $ \begin{array}{c|c|c|c} \hline Step & Stack & Input &...
2
votes
0answers
31 views

How to know a certain grammar is parse-able

Is it possible to parse all kinds of structured data and give them a semantic meaning? For example, C++ is a really complicated language and I could never imagine a parser would be possible for it. ...
1
vote
2answers
120 views

How to determine maximum stack size of LL(1) parser?

I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by ...
2
votes
1answer
91 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 ...
1
vote
1answer
127 views

How does SpaCy make its dependency tree?

I discovered that SpaCy had the ability to make dependency trees. For instance given a question “To whom did the Virgin Mary allegedly appear in 1858 in Lourdes France?” We can create its dependency ...
1
vote
1answer
160 views

What is handle in bottom up LR parsing?

I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows: Assume a rightmost ...
1
vote
1answer
91 views

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
2
votes
1answer
22 views

Marginalise edge weights on graph

I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a ...
0
votes
1answer
52 views

Can you automatically generate a parser for a type using type theory some how?

Was wondering since all the types are spelled out constructively, and the constructions can all be reflected symbolically on a computer, if you can automatically parse expressions in a type?
6
votes
1answer
66 views

Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?

The problem of determining, given a string $x$ and a context-free grammar $G$, whether $x \in L(G)$ is conjectured to take more than linear time in the length of $x$. Currently the best known ...
1
vote
0answers
279 views

Are LL(1) grammars a subset of LR(0) grammars?

As far as I've understood it seems that LL1 are a subset of LR0, but studying the following grammar I end up in a contraddiction. Grammar : S -> (S) | [S] | {S} | ε This is an LL1 while it seems ...
1
vote
1answer
32 views

Removing conflicts of LR(1) parsing tables

...
0
votes
0answers
80 views

Transform grammar into LL(1) left-associative

I was looking on some old exam questions for a course in my university, and stumbled upon an exercise that asked for the following: The starting grammar was this: ...