# Questions tagged [parsers]

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

384 questions
Filter by
Sorted by
Tagged with
258 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 ...
614 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 ...
609 views

3k views

### Need for an augmented grammar

The question is under the concept of LR parser. Suppose the original grammar is S->AA A->aA|b Is it necessary to add an additional rule S'->S to make it as augmented grammar? In short, I want to ...
698 views

1k 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 ...
390 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 ...
295 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 ...
342 views

117 views

### Can there be a context free language that is not recognizable by a PEG?

This is related to this question. Essentially, I want to know whether my reasoning is correct. We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: ...
130 views

### Why can we (apparently) implement CFG parsers only using (N)DFAs?

I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be nested. For parsing those files I ...
25 views

### Marginalise edge weights on graph

I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a ...
211 views

### Conversion of ambiguous left recursive grammar to LL(1)

I have been strugling with this LL(1) transformation for far longer than expected and am getting quite desperate. We are given a grammar $G = \left\{V_N, V_T, S, \Phi \right\}$, with the non-terminal ...
5k views

### Resolving ambiguity in dangling else

Initially the ambiguous grammar is as follows (with some cropped production rules): ...
63 views

### Tokenizer and complex operators

I'm trying to create simple tokenizer to transform following (only part shown) search expression to tokens word1 near(1) word2 where word1, word2 are some words ...
248 views

### Regular vs LALR(1): what is faster

Supposing we have two grammars which define the same languge: regular one and LALR(1) one. Both regular and LALR(1) algorithms are O(n) where n is input length. Regexps are usually preferred for ...
123 views

### Given an LR grammar G and a string w, is it possible to quickly find all substrings in w that are in L(G)?

Say I have an LR grammar G and a string w. I know that I can check if w is in the language of G in linear time. But what if w itself is not in the language of G, but I want to find all substrings of w ...