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
1answer
19 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 &...
1
vote
1answer
155 views

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
1
vote
1answer
99 views

How do I build a left derivation tree from an expression including right-to-left associativity?

Suppose I want to make a left derivation tree of an expression, but the expression includes operators that are right-to-left associative. Would I still expand the left-most variable first in my tree? ...
1
vote
2answers
132 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 ...
1
vote
1answer
42 views

Follow set confusion about inclusion

The book I am learning about compilers from states that $M \to \alpha N \beta$ will generate a constraint that $\mathrm{FOLLOW}(M)$ is contained in $\mathrm{FOLLOW}(N)$ when $\beta$ is nullable. This ...
1
vote
1answer
534 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?
1
vote
1answer
45 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
1answer
53 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 ...
1
vote
1answer
206 views

How to treat ϵ-productions in table-driven predictive parsing?

Here: https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html in chapter Driver Procedure, it's shown how table-drive predictive parsing works. The predict table however can ...
1
vote
1answer
402 views

Binary operators with higher precedence than unary operators

Generally (perhaps always) in programming languages, unary operators have the highest precedence. In some langauges, such as Standard ML, one can dynamically change the precedence of binary operators ...
1
vote
2answers
632 views

Can an LL(k) parser parse any grammar without left recursion or common prefixes?

I'm being asked to create a "top down grammar" for a certain language (I'm pretty sure there's no such thing as a "top down grammar" but I think it means write a grammar that an LL(k) parser can parse)...
1
vote
0answers
20 views

Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items. Is ...
1
vote
0answers
46 views

How to write “∀x.F(x)” for “F(x)=λx.Φ(x)” in one expression (sequel from question about “∀(λφ. (φ x m→ φ y))”?

This question is sequel from How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"? which further explains the notation and context. So - I have anonymous Boolean-valued ...
1
vote
1answer
31 views

Why is the following grammar not LL(1)

Consider the following grammar: S → bAb | bBa A → aS | CB B → b | Bc C → c | cC I have to provide the reasons as to why this grammar is not LL(1). So far ...
1
vote
1answer
24 views

Grammar still ambigous after removing left recursion LL(1)

I have following grammar it doesnt not have Epsilon-derivation problem I can only see left recursion: S -> a b S S -> S a b S -> c d S -> a d in ...
1
vote
1answer
58 views

Why table-driven LL (1) parser does not work with division and subtraction?

Everywhere, one grammar is used as an example table-driven LL(1) parser. Grammar ...
1
vote
0answers
27 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 ...
1
vote
0answers
95 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 ...
1
vote
0answers
35 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 ...
1
vote
0answers
17 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 ...
1
vote
1answer
77 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
30 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
129 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 ...
1
vote
0answers
19 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 ...
1
vote
0answers
360 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). ...
1
vote
0answers
648 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
104 views

Removing conflicts of LR(1) parsing tables

...
1
vote
0answers
421 views

Can a YACC parse an ambiguous grammar

I found a question while studying compilers :- Given a grammar E->E+E/E×E/number The above grammar is fed to a YACC with semantic rules for parsing. What will be the action of the YACC. 1) it ...
1
vote
0answers
80 views

Generate an AST from an indefinite grammar and logic

As said in the title, I have to generate an AST from a grammar and logic (or a"syntax" if you prefer). This grammar and syntax are both indefinite in the program, meaning that it is the user (a ...
1
vote
0answers
397 views

How do we evaluate semantic actions in L attributed SDT?

I came across following problem: $S→ER$ $R→∗E\{print(′∗′);\}R∣ε$ $E→F+E\{print(′+′);\}∣F$ $F→(S)∣id\{print(id.value);\}$ Here $id$ is a token that represents an integer and $id.value$ ...
1
vote
0answers
156 views

Can the HTML5 parsing algorithm be implemented in linear time?

Can the HTML5 parsing algorithm (https://html.spec.whatwg.org/multipage/parsing.html#parsing) be implemented in $O(n)$, or at worst $O(n\mathop{log}n)$, time, even for malicious input? It seems ...
1
vote
0answers
85 views

Where is left recursion in this little CF grammar?

S → D D → E | EC E → anyId C → B | .D | B.D B → <S> | <SA> A → ,S | ,SA The tool I am using keeps complaining about left recursion in this grammar. I ...
1
vote
0answers
209 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 ...
1
vote
0answers
41 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 ...
1
vote
0answers
192 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 ...
1
vote
0answers
75 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: ...
1
vote
0answers
93 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-...
1
vote
0answers
99 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 ...
1
vote
0answers
74 views

Parsing based on logical connectives and quantifiers?

What techniques exist for parsing sentences based on logical connectives and quantifiers? That is, for parsing sentences that are structured "around" logical connectives and quantifiers. E.g. [A] ...
1
vote
0answers
24 views

How equality of item (production state) is defined in LR parser?

Whenever I read about equality I took it for granted, but few days ago I wondered if my understanding is not too shallow. Consider such example (taken from: http://david.tribble.com/text/honalee.html):...
1
vote
0answers
502 views

LL(1) grammar for the untyped lambda-calculus

What I want to do I am trying to define a LL(1) grammar of the lambda-calculus. What I did Here is the grammar: $Term \to Abs$ $Term \to App$ $Abs \to \lambda \ id \ . \ Term$ $App \to Var \ ...
1
vote
0answers
718 views

What are the fundamental differences between predictive and LALR(1) parsers?

I'm reading the Dragon book. The beginning describes recursive descent parsers. Then it states that a predictive parser is the table version of a RD parser. I also read up on LALR(1) parsers. The ...
1
vote
0answers
208 views

LALAR vs SLR Table for Given SLR Grammar

i'm so glad that ask my first question on my favorite site. Infact i ran into multiple choice question in recent exam on Compiler Course. Suppose T1, T2 is created with SLR(1) and LALR(1) for ...
1
vote
0answers
511 views

LL(1) grammar for postfix ternary operations

Suppose the task is to make an LL(1) grammar for postfix operations, where the only operation is ternary. Obvious approach is $N$ - number $O$ - operation $S$ - expression rules:...
1
vote
0answers
244 views

Parsing Turing Machine

Have a question that requires me to write the rules for parsing a turing machine This is the question The PROBLEM involves writing a set of Turing Machine rules that will read and determine whether ...
1
vote
0answers
113 views

Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?

I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related. Suppose I have a regular expression: RE=(aa)?(aa) and I convert it to a grammar: G ::= A B A ::= C | (...
1
vote
0answers
81 views

what does “Configuration is valid for a viable prefix ” actually means?

I am learning LR(1) parsing from the Dragon Book. I am really confused with this sentence. Formally we say that a configuration $[A \to u•v, a]$ is valid for a viable prefix $α$ if there is a ...

1
4
5
6 7 8