algorithmparsingcontext-free-grammarlalrlr-grammar# Is there a general way to convert an unambiguous context-free-grammar into a LALR(1) grammar?

I am trying to create a LALR(1) parser for the following grammar and find some shift/reduce conflicts.

```
S := expr
expr := lval | ID '[' expr ']' OF expr
lval := ID | lval '[' expr ']'
```

So the parser can not parse the string "ID[ID]" correctly. My questions are,

- Are there any general ways to convert such non-LALR(1) grammars into LALR(1) grammars?
- If two grammars generate exactly the same languages and we know that one is not LALR(1), can we know if the other is LALR(1)?

The grammar mentioned above is only an example, what I really want to know is **general ways** to solve these grammar problems. Any suggestions or reading recommendations are welcome.

Thanks in advance.

Solution

1 . Are there any general ways to convert such non-LALR(1) grammars into LALR(1) grammars?

No. It may or may not be possible to convert an arbitrary context-free grammar (CFG) into an LALR(1) grammar. Moreover, if you have a CFG and an LALR(1) grammar, you cannot tell whether they recognize the same language. (Worse, there is no algorithm which will even tell you whether an arbitrary CFG recognizes every possible string for its alphabet.)

2 . If two grammars generate exactly the same languages and we know that one is not LALR(1), can we know if the other is LALR(1)?

Again, no. As above, there is no algorithm which can verify that two grammars generate the same language, but even supposing that you know that two grammars generate the same language, the fact that one of them is not LALR(1) tells you nothing about the other one.

There is, however, one useful result. If you have an LALR(k) grammar with finite k > 1, then you can generate an LALR(1) grammar. In other words, there is no such thing as an LALR(k) *language* for k > 1; if a language has an LALR(k) grammar, it has an LALR(k') grammar for any k' such that 1 ≤ k' < k.

That doesn't help you with your grammar, however, because the conflict cannot be eliminated by increasing lookahead to any finite value.

There is an easy way to get rid of that particular shift-reduce conflict, though, and it is a technique which often works. Consider the two conflicting rules:

```
lval := lval '[' expr ']'
expr := ID '[' expr ']' OF expr
```

The problem is that in the first case, `ID`

must be reduced to `lval`

immediately (or at least, before the following `expr`

is reduced), but in the second case it may not be reduced to `lval`

. But we can't tell which case we're in until we reduce the `expr`

and encounter the `OF`

(or not).

If we could finish the `lval`

production without doing the interior `lval`

reduction, then we wouldn't have a problem, because the actual reduction would happen when the token following the `]`

is visible.

There's probably a technical term for this, but I don't know it. I've always described it as "reduction deferral", and in many cases it is not very difficult:

```
lval' := ID `[` expr `]`
| lval' `[` expr `]`
lval := ID
| lval'
expr := lval
| ID '[' expr ']' OF expr
```

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?