# Questions tagged [parsers]

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

354 questions
Filter by
Sorted by
Tagged with
1k views

### Does precedence matter in constructing parse trees of arithmetic expressions for postfix notation?

Table 4 in Problem Solving with Algorithms and Data Structures's chapter on Infix, Prefix and Postfix Expressions gives the following examples: ...
26 views

### In top-down parser how do you match a product $A \rightarrow a_1 | a_2 | …$, $a_i$s terminals

One procedure for table-driven top-down parsing is given here: https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html This gives for matching the input the lines: ...
588 views

### What is the point of delimiters and whitespace handling

I see that language specifies reserved words, delimiters and whitespaces in the lexer section. Are delimiters just like reserved identifiers in the punctuation space or they have additioinal function ...
70 views

### Is C → A B C | A left-factorizable?

$$C \to A B C \mid A$$ Obviously has the same FIRST(C) for the both productions. But how can this be left-factorised? Tried: $$C \to A B C'$$ $$C' \to A C \mid \varepsilon$$ The FIRST sets are ...
122 views

### Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$

With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$ I need to: run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can ...
131 views

### Are parser combinators equivalent to scannerless parsing?

From what I can see, parser combinators are equivalent to scannerless parsing. I do not see this stated in implementations of scannerless parsing page, nor in the parsing combinators page, neither in ...
258 views

### Automata vs Earley parsing? [closed]

If the language is implementable as mere DFA (i.e. it's a regular language), then why would one need a parsing algorithm such as Earley. Regular languages are a subset of context-free languages, but ...
185 views

### In NLP, does the lexer have to tag the tokens before the parser?

In NLP, does the lexer have to tag the tokens before the parser? I.e. does the lexer have to classify the tokens to morphological categories before the parser? I'm thinking yes, but is this also the ...
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 ...
44 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 ...
385 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 ...
67 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 ...
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] ...
2k 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 ...
592 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 '(' ...
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 ...
144 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 ...
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-...
258 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 ...
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: ...
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 ...
337 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 ...
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):...
157 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 ...
140 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, ...
271 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 ...
256 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 ...
844 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 ...
520 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 ...
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-...
500 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 ...
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 ...
542 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....
299 views

164 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 = ...
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 ...
74 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/...
221 views

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. ...
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?
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 ...
163 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 &\...
527 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 ...
3k 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 ...