parsinglr-grammarlr1# LR(1) item sets for left recursive grammar

I read several papers about creating LR(1) item sets, but none of them pertained to left recursive grammars, such as those used for parsing expressions. If I had the following grammar,

```
E -> E + T | T
T -> T * F | F
F -> (E) | NUMBER
```

How would I go about creating the LR(1) item sets?

Solution

Left recursion isn't inherently a problem for LR(1) parsers, and the rules for determining the configurating sets and lookaheads is the same regardless of whether your grammar has left recursion.

In your case, we begin by augmenting the grammar with our new start symbol:

```
S -> E
E -> E + T | T
T -> T * F | F
F -> (E) | NUMBER
```

Our initial configurating set corresponds to looking at the production `S -> E`

with a lookahead of `$`

. Initially, that gives us the following:

```
(1)
S -> .E [$]
```

We now need to expand out what E could be. That gives us these new items:

```
(1)
S -> .E [$]
E -> .E + T [$]
E -> .T [$]
```

Now, let's look at the item `E -> .E + T [$]`

. We need to expand out what `E`

could be here, and the rules for doing so are the same as in the non-left-recursive case: we list all productions for `E`

with the dot at the front, with a lookahead given by what follows the `E`

in the production `E -> .E + T [$]`

. In this case we're looking for an `E`

with a lookahead of `+`

because that's what follows is in the production. That adds these items:

```
(1)
S -> .E [$]
E -> .E + T [$]
E -> .T [$]
E -> .E + T [+]
E -> .T [+]
```

From here, we expand out all the cases where there's a dot before a `T`

, which gives the following:

```
(1)
S -> .E [$]
E -> .E + T [$]
E -> .T [$]
E -> .E + T [+]
E -> .T [+]
T -> .T * F [$]
T -> .F [$]
T -> .T * F [+]
T -> .F [+]
```

We now have to expand out the `T`

s in the context of `T -> .T * F [$]`

, and we do so by listing all productions of `T`

followed by what the `T`

is followed by in `T -> .T * F [$]`

(namely, `*`

). That gives us the following:

```
(1)
S -> .E [$]
E -> .E + T [$]
E -> .T [$]
E -> .E + T [+]
E -> .T [+]
T -> .T * F [$]
T -> .F [$]
T -> .T * F [+]
T -> .F [+]
T -> .T * F [*]
T -> .F [*]
```

And from here we'd expand out the productions that have a dot before the `F`

. Do you see how to do that based on how things have played out so far?

- Firestore JSON parsing terminated
- Why is string.Empty more recommended than ""?
- How to escape braces (curly brackets) in a format string in .NET
- How to strip all non-alphabetic characters from string in SQL Server?
- Tree of all dependencies in a SQL Server database
- android parsing negative number strings
- Using ANTLR 3.3?
- Date value wrongly formatted
- Parsing JSON array into java.util.List with Gson
- @username Regular Expression for social media with JavaScript
- Content Security Policy report-uri is not being recognized
- Python Json loads() returning string instead of dictionary?
- Parsing JSON in Excel VBA
- SQL: parse the first, middle and last name from a fullname field
- parse URL with JavaScript or jQuery
- Dump all key pair of a json with JQ
- Read data from a txt file into 2D array python
- Blending a LaTeX document with python package pylatexenc
- Unpack / pack operator
- DateTime.TryParseExact constantly returns false
- How to check that a string is parseable to a double?
- Python urlparse -- extract domain name without subdomain
- How to consume W3C EBNF-Notation and produce a parser generator?
- DurationPattern can't parse without separator
- try to parse a simple "\s*identifier\s+identifier\s+identifier\s*" string
- How to extract data from a PDF file while keeping track of its structure?
- C++ alternative for parsing input with sscanf
- Beautiful Soup - Get all text, but preserve link html?
- How does `substitute` choose the deparsed representation of objects?
- How to convert Python List into ast.List?