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
35 views

Duplicating the quotation marks in in the quotation-mark enclosed strings

There is such a grammar string_literal ::= " { graphic_character } " The double-quotes that you see must appear in the user program and curly braces mean "any ...
1
vote
1answer
39 views

How to detect plurals in English sentences?

I'm wondering how to detect English plurals in natural language sentences. Such as: fish computers houses ... Using Earley parsing I'm able to get to the s or no-s, but I have difficulties in ...
-2
votes
1answer
370 views

How should I show that a grammar is not LL(1) and convert grammar to LL(1)

I'm trying to find the ambiguity in this grammar so I can remove it and convert it to LL(1), however for the life of me, I can't find the ambiguity. Moreover, I think there is cycle between X and Y ...
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 ...
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] ...
0
votes
1answer
1k views

What exactly is the LL(k) grammar condition?

I have a bit of trouble understanding the definition of LL(k) grammars. Here it's defined as: for every pair of production rules $A\rightarrow α$ and $A \rightarrow β$ the following ...
0
votes
1answer
579 views

Construct SLR Parse table problems

Consider the augmented grammar G is: S` -> S S -> a S -> (T) T -> T,S T -> S I have tried to construct parse table. But, when I read '(' ...
2
votes
1answer
62 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 ...
4
votes
1answer
140 views

An intuitive explanation for LR grammars?

With LL grammars, there seems to be a very intuitive explanation, in terms of first and follow tables.( The first letter/s encountered in a particular state, can only mean a particular rule). With LR ...
3
votes
1answer
2k views

Ambiguous Grammar and SLR parsing table : No conflicts?

We have been studying the development of SLR parsers, and that now we have done the arithmetic expression grammar (the unambiguous version), I was curious to see if the same could be done to the if-...
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 ...
0
votes
0answers
74 views

Linear time parsing from star of context free language

I was wondering if there are cases in which the star closure of a language can make the resulting language easier to parse. In particular, if I have this grammar: ...
16
votes
2answers
1k views

For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar?

Apparently, ReDos attacks exploit characteristics of some (otherwise useful) regular expressions ... essentially causing an explosion of possible paths through the graph defined by the NFA. Is it ...
1
vote
1answer
303 views

Whats 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 Problems here. First the L rules are a left recursion ...
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):...
0
votes
1answer
149 views

Chomsky NF or Greibach NF benefits for LR parser?

Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind: total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating ...
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, ...
10
votes
1answer
261 views

Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?

There's a way to perform fuzzy parsing (accepts strings even with typos to a certain edit distance), with a DFA and a run-time constructed Levenshtein Automata of the input word. Can something ...
2
votes
1answer
247 views

fixed point in regular expressions

I've posted this question first on StackOverflow but this section seems more suited for this kind of questions. Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll ...
3
votes
3answers
808 views

What techniques can I use to hand-write a parser for an ambiguous grammar?

I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a ...
10
votes
2answers
488 views

How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which ...
12
votes
2answers
2k views

Removing left-recursion in grammar while maintaining left-association of operator

I have a problem with this exercise: Let G be the following ambiguous grammar for the λ-calculus: E → v | λv.E | EE | (E) where E is the single non-...
0
votes
1answer
483 views

How do I form a parse tree for equations? [closed]

I have the following equation if (x > y) { if (y < a) { x:= a y:= b } else { x:= b; } } I was thinking of something like this ...
5
votes
1answer
2k views

Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators?

Consider a grammar G which is SLR(1) except for some shift/reduce conflicts which can be resolved by imposing some precedence or associativity of operators. Is it the case that the construction of ...
4
votes
1answer
525 views

What is a real-world use-case/need for a left-recursive grammar?

I understand the basics of how left-recursion works, and why some people say it's bad. And I've also ready opinions such as: ...like LL and LR parsing, PEGs are often frustrating to use in practise....
1
vote
1answer
293 views

CFGs: detecting infinitely many derivations of a single string

Some particularly degenerate CFGs can produce a single string in infinitely many ways: for a dumb example, $S \to SS \mid \epsilon$ can produce the empty string as $S \to \epsilon$ or $S \to SS \to S \...
1
vote
0answers
461 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 \ ...
0
votes
1answer
154 views

How to create an LR($k$) grammar for a given language?

How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say: $$L=\left\{w \in \{a, b\}^\star \ | \ \exists u \in \{a, b\}, v \in \{a, b\}^\star: w = ...
15
votes
1answer
4k views

Why separate lexing and parsing?

It's possible to parse a document using a single pass from a state machine. What is the benefit of having two passes, ie. having a lexer to convert text to tokens, and having a parser to test ...
0
votes
1answer
73 views

LL(k) Prediction Techniques (and Insight on method applied)

I'm requesting references for LL(k) in situations where k > 1 for reasons described below. I'm looking for research/notes/...
0
votes
2answers
218 views

generating recursive descent parser

I have a grammar, $L \to A \langle A \rangle^*$ $A \to () \mid (L)$ but I am not sure how to generate parser for $\langle A \rangle$. I know in other case, for example, if $E \to T \langle^*T\...
0
votes
1answer
376 views

Are regular grammars always LR(1)

The question is fairly straight forward. I just found a question on the internet that asks whether all regular grammars are LL(1) LR(1) I guess they can't be LL(1) because of left recursion, but how ...
2
votes
1answer
1k views

Why we use context-free grammar for parsing?

Why we use context-free grammar for parsing? Why not regular expression and not context-sensitive grammar?
0
votes
2answers
2k views

Computing FOLLOW sets for LL(1) grammar. Stuck on question

Calculate the FOLLOW sets for all the non terminals: $S \rightarrow bEx \mid Db \mid b \mid F$ $D \rightarrow EDc \mid Y$ $E \rightarrow dED \mid dDY$ $Y \rightarrow ab \mid aDx \...
1
vote
2answers
2k views

Is this grammar LALR(1)

I am working through creating a LALR(1) parser generator. I have the following grammar which I designed to highlight the epsilon for rule 3. ...
1
vote
2answers
124 views

Min-Max number of shifts and reductions in bottom-up parser [closed]

Given the Grammar has no unit or ɛ-productions, What is minimum & maximum number of shifts and reduce needed by bottom-up parser?
1
vote
2answers
92 views

How can this grammar parse such an input?

I've an example which I simply don't get at all. Implement an attributed grammar that checks that either the word ends in $b$ or each prefix of the word contains at least as many $b$s ...
-1
votes
1answer
156 views

Is this $LL(1)$ grammar valid?

Is the following a valid $LL(1)$ grammar: $ \begin{align} S &\rightarrow L \$ \\ L &\rightarrow M L_2 \\ L_2 &\rightarrow \underline{::} L \\ L_2 &\rightarrow \epsilon \\ M &\...
0
votes
2answers
482 views

Relation between CLR Grammar and Ambiguity

I am studying CLR Parser and have a query about Grammar. If a Grammar can't be parsed using CLR(1) Parser ( i.e LR(1)) parser is it necessarily ambiguous? Is it possible that a grammar which is ...
2
votes
1answer
2k views

LALR(1) parsers and the epsilon transition

I am having trouble getting my head wrapped around epsilon transitions while creating an LALR(1) parse table. Here's a grammar that recognizes any number of 'a' followed by a 'b'. 'S' is an ...
0
votes
0answers
60 views

Can we say we reduced a rule if we reduced an equivalent set of smaller rules?

I have constructed an SLR(1) parsing table with the following rules. S -> S + S + S (rule 1) S -> S + S (rule 2) S -> y Is reducing rule 2, then shifting + and y, then again rule 2, equivalent to ...
0
votes
1answer
62 views

Given family of grammars, determine if LR(k)

Parsing family of grammars, determine if LR(k) I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him ...
0
votes
1answer
332 views

How does the Earley Parser store possible parses of an ambiguous sentence?

I've got a pretty basic question concerning the Earley parser: In case of syntactic ambiguity ( S -> NP VP(V NP(NP PP)) vs. S -> NP VP(VP((V NP) PP) ), are both parses stored in one chart or in two? ...
0
votes
2answers
3k views

Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?

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, Consider the following six classes of languages: Context free (...
10
votes
3answers
5k views

Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$

Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed ...
2
votes
1answer
4k views

Resolving ambiguity in dangling else

Initially the ambiguous grammar is as follows (with some cropped production rules): ...
5
votes
1answer
958 views

Is CYK still relevant today?

I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today. Is it or an extension of it still being used in compilers (for example), or have other ...
0
votes
1answer
706 views

LR(0) expressive power

So I have grouped the following formalisms into a power hierarchy (and made classes for them): Class 1 DFA NFA NFAϵ reg.exp Class 2 (DCFL expressivity?) LR(1) DPDA Class 3 CFG PDA Class 4 TM ...
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 ...