Menu
I know the basic differences of LL vs LR parsers. I also know that GLR, SLR, and LALR are all extensions of LR parsers. So my question in more details is...
Given a LL(*) parser and any variation on a LR parser, is there any language that can be described in one and not the other? Or more simply is there any feature or property that can not be expressed with either?
As a concrete example. If I were to create a language using an LL(*) parser, will I ever run into desired feature/property that I might want to add to my language that would only be possible with a LR parser (or vice versa)?
418
LR parsers can usually recognize all programming language construct that can be specified by context-free grammars. LR parsers detect errors fast. Drawback: it is too much work to construct an LR parser by hand. Fortunately, we can use an LR parser generator such as YACC.
LR parsers can handle a larger range of languages and grammars than precedence parsers or top-down LL parsing. This is because the LR parser waits until it has seen an entire instance of some grammar pattern before committing to what it has found.
At a high level, the difference between LL parsing and LR parsing is that LL parsers begin at the start symbol and try to apply productions to arrive at the target string, whereas LR parsers begin at the target string and try to arrive back at the start symbol. An LL parse is a left-to-right, leftmost derivation.
LR parser can accept bigger class of languages than LL. In LL(k) and LR(k), k means number of lookahead symbols that it needs to know so it can apply appropriate production/reduction. The bigger k get, the bigger are parsing tables. So k is not limiting only LR parsers, it is limiting LL parsers, too. The reason why LR parser can accept bigger class of languages is because of left recursion that are problematic when working with LL parsers. But this is not true entirely, because direct recursion are solvable, meaning that you can rewrite the grammar to be LL grammar. Direct recursion is something like A -> Abc. When you have indirect recursion, for which you now probably know how it looks, then you have a problem. LR parsers can solve this issues because they make parse tree in bottom-up manner. You will have to look little bit deeper into LR parsing to see why is that exactly. But, LR parsers are not all mighty, they have limitations, too. Some grammars are very difficult to digest and k factor does not help. For this kind of grammars GLR parser is needed, which actually simulates LR(k) parser but uses backtracking to analyze entire parse space when production/reduction ambiguity occurs.
66
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
