Questions tagged [parsers]

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

89 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
1answer
311 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 ...
8
votes
0answers
252 views

Can any PEG grammar be parsed in linear time?

On the Wikipedia for PEG it is claimed: Any PEG can be parsed in linear time by using a packrat parser, as described above. However, packrat parsers can't handle left recursion. You can eliminate ...
6
votes
0answers
66 views

Is THEADS the same as FIRST?

I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph: We will first of all briefly review the LR(1) parsing and ...
4
votes
0answers
507 views

How does this left-associative recursive descent parser work?

For personal enlightenment, I'm trying to write a recursive descent parser for lambda calculus without abstraction, i.e., just identifiers and function application. The BNF grammar that describes the ...
4
votes
0answers
144 views

How does Earley parsing using an automaton work?

As described in this paper, you can use an pre-computed automaton to speed up an Earley parse. I'm not interested in the rigorous proof of this, but just how the basic algorithm works so that I can ...
4
votes
1answer
134 views

Are there automatic transformation of grammar algorithms?

From time to time you can write a grammar that creates shift/reduce conflict (for example) but after reading the grammar you notice that if you rewrite the productions the conflict will go away, ...
3
votes
0answers
27 views

How to model grammar ambiguity

Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings. Practically, ...
3
votes
0answers
204 views

How would I build a parser generator for a context free grammar using Pushdown Automata?

I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc. I am at the point where I have lexer generation ...
3
votes
0answers
100 views

Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?

Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing? The ...
2
votes
0answers
46 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
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. ...
2
votes
0answers
69 views

Expanding an Earley parse forest

I have a small context-free grammar, which I would like to use to turn input strings into parse trees. I need to get all possibilities in case of ambiguity (so shift-reduce is out), and there's quite ...
2
votes
0answers
82 views

Examples of context-free grammars with worst-case complexity

What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers? I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would ...
2
votes
0answers
309 views

SLR vs CLR parser

In SLR we use follow set of a non terminal for determining reduce moves and in CLR we use lookaheads for the same. How does using lookaheads actually help in improving the performance of the parser ? ...
2
votes
0answers
55 views

Correct bracketing check with rotate operation on position i

Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations: Check whether the sequence is correctly bracketed Rotate bracket ...
2
votes
0answers
266 views

How to find conflicts in LALR parser?

I have a LR analyser and I can't find out how to know whether the grammar is or is not LALR(1). I think that I have to merge states with the same rules. So I have to merge states: $2 - 12, 3 - 13, 4 -...
2
votes
0answers
723 views

lexical scoping vs. dynamic scoping

I'm wondering about the result of this program as I get confused when it comes to lexical scoping and dynamic scoping. ...
2
votes
1answer
204 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 ; ...
2
votes
0answers
568 views

Parsing family of grammars, determine if LR(k)

Consider the family of grammars $G_n,~n\geq2$. $$S \rightarrow A_ib_i~,~for~~1\leq i \leq n$$ $$A_i \rightarrow a_jA_i~|~a_j~,~for~~1 \leq i,j \leq n~~and~~i \neq j$$ where multiple alternative right ...
1
vote
0answers
53 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: ...
1
vote
0answers
26 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
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 ...
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 ...
1
vote
0answers
24 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
94 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
17 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
187 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
433 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
0answers
323 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
63 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
2answers
104 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
0answers
135 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
82 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
171 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
174 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
66 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
96 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
145 views

Upper bound of automaton states for SLR parsing

How do I tell, given a specific grammar, which is the upper bound for the number of states of a LR(0) or LR(1) automaton for its SLR parsing? My guess is that generating the canonical item collection ...
1
vote
0answers
73 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
23 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
460 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
713 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
203 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
474 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
98 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
80 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 ...