17.5 LR(1) PARSING ALGORITHM

Here is the LR(1) Parsing Algorithm that uses the LR(1) Parse Table with a stack to parse strings. For this stack we do not use a stack start symbol, but instead assume this stack can determine whether it is empty or not. An entry in the LR(1) Parse Table has possible multiple parts including an action (s for shift, r for reduce, g for goto, acc for accept, or e for error), a state, a right-hand side (rhs) of a production, and a left-hand side (lhs) of a production. The functions get(), top(), pop(), and push() were defined in Section 16.2.

LR(1) Parsing Algorithm

Program code. Line 1: state, equals, 0. Line 2: push, left parenthesis, state, right parenthesis. Line 3: look ahead, equals, get, left parenthesis, right parenthesis. Line 4: entry, equals, L R, left bracket, state, comma, look ahead, right bracket. Line 5: while, entry, dot, action, equals, equals, s, or, entry, dot, action, equals, equals, r, colon. Line 6, indented once: if, entry, dot, action, equals, equals, s, then, colon. Line 7, indented twice: push, left parenthesis, look ahead, right parenthesis. Line 8, indented twice: look ahead, equals, get, left parenthesis, right parenthesis. Line 9, indented twice: state, equals, entry, dot, state. Line 10, indented twice: push, left parenthesis, state, right parenthesis. Line 11, indented once: else, colon, forward slash, forward slash, entry, dot, action is r. Line 12, indented twice: for, size, left parenthesis, entry, dot, r h s, right parenthesis, asterisk, 2, do, colon. Line 13, indented 3 times: pop, left parenthesis, right parenthesis. Line 14, indented twice: state, equals, top, left parenthesis, right parenthesis. Line 15, indented twice: push, left parenthesis, entry, dot, l h s, right parenthesis. Line 16, indented twice: entry, equals, L R, left parenthesis, state, comma, entry, dot, l h s, right bracket. Line 17, indented twice: state, equals, entry, dot, state. Line 18, indented twice: push, left parenthesis, state, right parenthesis. Line 19, indented once: entry, equals, L R, left bracket, state, comma, look ahead, right bracket. Line 20: if, entry, dot, action, equals, equals, a c c, and, look ahead, equals, equals, dollar, then. Line 21, indented once: accept, string. Line 22: else, colon. Line 23, indented once: error.

Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial