# Tagged Questions

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

15 views

### LL(k) vs Strong LL(K)

What is the diference between LL(K) and strong LL(K) grammars definitions? LL(k): For every pair of production rules A→α and A→β the following condition holds. FIRSTk(αy) ∩ FIRSTk(βy) = ∅ ...
12 views

### Which implementation algorithms in the updated Lexers and Parsers are more advanced and efficient? [closed]

I want to write a lexer and parser based on C# language in new microsoft framework .NET Core. So I have investigation about the knowledge of implementation similar libraries. Comparison of parser ...
39 views

### Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
44 views

33 views

### Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?

Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators? This question seems very trivial, but I don't know ...
36 views

### Can valid sub-parses be added to an earley chart after a successful parse has been recognized?

I'm implementing the Earley algorithm and am trying to build a parse forest from the output of the recognizer. However in the process of doing so I got this output from an ambiguous CFG, where a non-...
49 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 ...
36 views

31 views

### Indirect Left recursion

I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol. S -> Aa / a eq1 A -> Sb / b. eq2 Now I can do this in two ...