Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
69 views

Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?

I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that ...
0
votes
1answer
20 views

how to formally arrive at a correct EBNF grammar of a language

I am trying to write a mini parser for a simple language whose specification is as follows: A search term is represented by. Both searchkey and ...
0
votes
2answers
37 views

Is this an LL(1) grammar? How to solve First - Follow conflict?

im trying to check if this grammar is LL(1). S -> L = R L -> * L | id R -> L | R + R | num As you can see there is a Left recursion on R production. So i remove that and what i get is: S -> L = ...
1
vote
1answer
21 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 ...
0
votes
1answer
42 views

What is the time complexity of finding the FIRST and FOLLOW sets?

Given how important these are for parsing, I'm surprised I wasn't able to find anything about their complexity. I'm interested in all combinations of: What is the (edit: best known) time complexity ...
10
votes
1answer
350 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 ...
-2
votes
1answer
31 views

Computing FIRST and FOLLOW

Given the following grammar with terminals $VT=\{[,],a,b,c,+,-\}:$ $S \rightarrow [SX]|a$ $X \rightarrow +SY|Yb|\epsilon$ $Y \rightarrow -SXc|\epsilon$ This should be the FIRST function: ...
0
votes
0answers
16 views

Abstract syntax tree: expression->operation->lhs|rhs vs expression->lhs|operation|rhs - what should I take into account in decision?

I am trying to build class hierarchy for the abstract syntax tree of First Order Logic as specified in the grammar https://github.com/antlr/grammars-v4/blob/master/fol/fol.g4 (ANTLR parser generator). ...
1
vote
1answer
21 views

Defining Grammar for Given Language

I'm attempting to practice for an exam and I'm having some trouble on one of the practice problems. The problem asks to identify a variety of language as regular grammar, context-free grammar, context-...
0
votes
1answer
7k 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
91 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 ...
2
votes
1answer
977 views

Indirect Left recursion

I'm resolving indirect left recursion for these production rules: S -> Aa / a eq1 A -> Sb / b. eq2 Where S is the ...
0
votes
1answer
2k views

Computing FOLLOW sets for a LL(1) grammar

I am trying to learn compiler design. But I get confused when I have to deal with computing the follow set specifically for the empty word. Given the grammar: ...
2
votes
1answer
222 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
124 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
45 views

Would the following grammar be ambiguous?

I have the grammar $S = aSbS|bSaS|\varepsilon$. When I was first looking at the problem I thought it was unambiguous. When I looked at the answer it said that it was ambiguous. The solution it gave ...
0
votes
1answer
38 views

Grammars and Parsing: Ambiguity in Sequences

BACKGROUND I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches. Given terminals: "a": KEYWORD "b": ...
0
votes
1answer
18 views

Why shift means push terminal symbol and state into the stack? Why not push only state?

Shift means that you need to put the status and terminal symbol on the stack. But what is the terminal symbol used for? After all, if the reduce command is executed, both the state and the terminal ...
1
vote
1answer
26 views

Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?

I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars. However, I've encountered this statement from my notes: With $\epsilon$ productions in the ...
0
votes
1answer
30 views

How can I determine the start non-terminal of a CFG?

Suppose I have a grammar such that there exist $n$ production rules which contain only terminal symbols, and none of these rules produce the same terminal (disjoint). $A ::= x|y|z$ $B ::= a|b|...
0
votes
1answer
441 views

LL1 parsing algorithm for strings generated by a given grammar

How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar? I have to design a parser for a specific grammar. Let $G$ be the grammar described as: $$S \...
3
votes
3answers
3k views

Is this language LL(1) parseable?

I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language. $$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$ Is my hypothesis true ...
1
vote
1answer
53 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 ...
0
votes
1answer
18 views

Build LL(1) parsing table for grammar S -> iSeS | iS | a

Task Bulid parsing table for grammar S -> iSeS | iS | a Resolve conflicts in this table and simulate parser work for word ...
2
votes
1answer
124 views

What is the relation between parsing languages and checking languages?

I have looked at a number of textbooks on computability theory. They typically have the following form: Define a language class (regular, context-free, context-sensitive, recursively enumerable) ...
10
votes
3answers
2k views

Representing “but not” in formal grammar

I just came across the following grammar definition: CommentChar ::       SourceCharacter but not LineTerminator But for discussion, I'll present this similar ...
0
votes
1answer
47 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
1answer
127 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 (...
-1
votes
1answer
50 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 ...
3
votes
0answers
35 views

Algorithm for undirected projective dependency parsing

I am looking for an algorithm that will get an optimal projective undirected dependency parse. That is, given the sentence 'Mary does love John', and an edge-weight function $f$ (that is, a function ...
0
votes
1answer
54 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
20 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
468 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
21 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
322 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
30 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
54 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
100 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
358 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
62 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
173 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
79 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
30 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 ...
1
vote
1answer
421 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
195 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
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
193 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
34 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....

1
2 3 4 5
8