1
$\begingroup$

I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).

For part of an assignment I had to form the DFA for a grammar, which I had no issues with. And then I have been asked whether the grammar is LR(0). My guess is yes, but not because I understand exactly what it means. I would assume it isn't if, when creating the DFA I came across some strange behaviors that prevented the DFA making any sense (if you know what I mean/if I'm making any sense).

$\endgroup$
9
$\begingroup$

A bottom-up parsing technique, used for parsing most context-free grammars is LR(k): L indicates that the input is parsed from left to right, R indicates that in the parsing process a rightmost derivation is produced; the number k indicates how many lookahead symbols are used.

An LR parsing scheme consists of: input, output, stack, a parsing program and a parsing table divided into two parts (actions (shift, reduce) and goto).

The idea is that the parsing program reads characters from an input buffer one at a time and uses the stack to store strings of the form s0X1s1X2s2...smXm where s0 is the initial state, the only one present at the beginning of the computation on the stack, while sm is the state at the top of the stack. Each Xi is a grammatical symbol while each si is a symbol that identifies a state. Each state describes the information contained in the stack before it; the combination of the state at the top of the stack and the current input symbol is used to index the parsing table and to determine the parser's shift-reduce decisions.

Given a grammar, to prove that this is LR(0) builds the DFA of viable prefixes. The first prefix is always S' -> .S because we consider the grammar increased. Then follow the rules to build the LR(0) parsing table.

A grammar is LR(0) if each position in the parsing table LR(0) contains at most one element.

Furthermore, the LR(0) languages all enjoy the prefix property. So if a language does not have this property, we can immediately say that it is not LR(0).

If the grammar is ambiguous then it cannot be LR(k) for any k.

$\endgroup$
  • $\begingroup$ Ah, it all makes sense. It's more information than I needed, but I am grateful nonetheless. $\endgroup$ – Jake Jackson Nov 9 '20 at 18:27
  • 2
    $\begingroup$ I tried to give the best possible answer given my knowledge :) $\endgroup$ – ElidorDD Nov 9 '20 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.