Во многих отношениях парсер LR (2) работает аналогично парсеру LR (1). Он отслеживает крайнее правое происхождение в обратном порядке, поддерживает стек, выполняет действия сдвига и сокращения в стеке, имеет состояния, которые состоят из наборов элементов LR и т. Д. c. Однако есть несколько основных отличий:
- Парсер LR (2) поддерживает два токена просмотра вперед для каждого элемента LR, а не только один токен просмотра вперед, как в LR (1).
- Правила работы сдвига отличаются от стандартных правил парсера LR (1) и требуют дополнительного понятия опережающего просмотра, называемого точечного опережающего просмотра , которого нет в парсерах LR (1).
- Ширина таблицы действий для парсера LR (2) намного больше, чем у парсера LR (1), хотя, как это ни парадоксально, таблица goto имеет такую же ширину.
Чтобы понять, как это работает, давайте возьмем пример грамматики LR (2). (Эта грамматика взята из грамматики, упомянутой в @ rici превосходном ответе на этот более ранний вопрос ).
S → RS | R
R → abT
T → aT | c | ε
Чтобы построить наш парсер LR (2) для этой грамматики, мы начнем, как обычно, с дополнения грамматики, создав форму S '→ S:
S '→ S
S → RS | R
R → abT
T → aT | c | ε
Теперь приступим к созданию конфигурационных наборов. Мы начинаем, как и в случае с парсером LR (1), с продукции S '→ S. Это показано здесь:
(1)
S' -> .S [$$]
Обратите внимание на то, что опережающий просмотр равен $$, что указывает на две копии "конца". маркер "потока". В традиционном синтаксическом анализаторе LR (1) (или SLR (1), или LALR (1)) у нас будет предварительный просмотр здесь $, всего одна копия маркера конца потока.
Теперь мы начинаем расширять другие элементы в этом наборе конфигурации. Поскольку у нас есть производства S → RS и S → R, мы добавляем следующие элементы:
(1)
S' -> .S [$$]
S -> .R [$$] // New
S -> .RS [$$] // New
Теперь давайте начнем следить за тем, что произойдет дальше. Как и в парсере LR (1), поскольку здесь есть точки перед нетерминальными буквами R, нам нужно их развернуть. Как и в разборе LR (1), при этом нам нужно определить, какие опережающие просмотры использовать. Мы начнем с расширения элемента S -> .R [$$], например:
(1)
S' -> .S [$$]
S -> .R [$$]
S -> .RS [$$]
R -> .abT [$$] // New
Затем давайте расширим параметр S -> .RS [$$]. Это интересный случай. Нам нужно определить, как будет выглядеть опережающий поиск для обнаруженных здесь R-продуктов. В парсере LR (1) это можно найти, просмотрев ПЕРВЫЙ набор оставшейся части продукции. В парсере LR (2), поскольку у нас есть два токена просмотра вперед, мы должны искать FIRST 2 set , который является обобщением FIRST множеств, в котором перечислены строки длина два, которые могут появиться в начале постановки, а не строки длины один, которые могут появиться там. В нашем случае FIRST 2 (S) = {ab} (вы понимаете, почему?), Поэтому у нас есть следующее:
(1)
S' -> .S [$$]
S -> .R [$$]
S -> .RS [$$]
R -> .abT [$$]
R -> .abT [ab] // New
На этом мы закончили расширение первого набора конфигурации. Пришло время подумать, что бы мы сделали, если бы в следующий раз увидели других персонажей. К счастью, в данном случае это довольно просто, поскольку первым символом любой строки, создаваемой этой грамматикой, должен быть a. Итак, давайте посмотрим, что произойдет, если мы встретим a:
(2)
R -> a.bT [$$]
R -> a.bT [ab]
Пока что все в порядке. Что произойдет, если мы увидим здесь b? Это приведет нас к следующему месту:
(3)
R -> ab.T [$$]
R -> ab.T [ab]
Здесь есть два элемента LR (2), у которых есть точки перед нетерминалом, поэтому нам нужно расширить их. Давайте начнем с расширения их для R -> ab.T [$$], получив следующее:
(3)
R -> ab.T [$$]
R -> ab.T [ab]
T -> .aT [$$] // New
T -> .c [$$] // New
T -> . [$$] // New
Затем мы расширим производство для R -> ab.T [ab]:
(3)
R -> ab.T [$$]
R -> ab.T [ab]
T -> .aT [$$]
T -> .c [$$]
T -> . [$$]
T -> .aT [ab] // New
T -> .c [ab] // New
T -> . [ab] // New
Это заполняет это набор для настройки. Это первый раз, когда мы находим некоторые завершенные элементы сокращения (здесь T -> . с двумя разными опциями просмотра). У нас также есть несколько сменных предметов. Поэтому мы должны спросить - есть ли здесь конфликт сдвига / уменьшения или конфликт уменьшения / уменьшения?
Начнем с конфликтов уменьшения / уменьшения. Как и в случае парсинга LR (1), у нас есть конфликт уменьшения / уменьшения, когда есть два разных элемента сокращения (элементы с точкой в конце) с одинаковыми опережающими взглядами. Здесь у нас есть два разных элемента сокращения, но у них разные опережения. Это означает, что у нас все в порядке с фронтом уменьшения / уменьшения.
Теперь интересный случай. Есть ли здесь конфликты сдвига / уменьшения? Здесь все немного меняется по сравнению с анализом LR (1). Как и в случае анализа LR (1), мы смотрим на все элементы сдвига в нашем наборе (элементы с точкой перед терминалом) и все элементы сокращения в нашем наборе (элементы с точкой в конце). Мы ищем, есть ли конфликты:
T -> .aT [$$] // Shift
T -> .c [$$] // Shift
T -> . [$$] // Reduce
T -> .aT [ab] // Shift
T -> .c [ab] // Shift
T -> . [ab] // Reduce
Вопрос, однако, в том, как здесь выглядит конфликт сдвига / уменьшения. В синтаксическом анализаторе LR (2) у нас есть два токена просмотра вперед, на которых мы принимаем решение о том, сдвигать или сокращать. В случае с элементами сокращения легко увидеть, какие два токена просмотра вперед заставят нас уменьшить - это двухсимвольный просмотр вперед в скобках. С другой стороны, рассмотрим сменный элемент T -> .c [ab]. Что это за двухсимвольный взгляд вперед, в котором мы бы переместились? В случае парсера LR (1) мы бы просто сказали: «О, точка стоит перед c, поэтому мы переходим на c», но здесь этого недостаточно. Вместо этого мы бы сказали, что опережающий просмотр, связанный с этим элементом сдвига, равен ca, причем c поступает из самого производства, а a - от первого символа опережающего просмотра элемента.
Аналогично рассмотрим сменный элемент T -> .aT [$$]. Нам нужны два символа просмотра вперед, и мы можем довольно легко увидеть один из них (a после точки). Чтобы получить второе, мы должны посмотреть, что может производить T. Есть три продукции для T: одна заменяет T на ε, вторая заменяет T на aT и третья заменяет T на c. Это означает, что любая строка, которая может быть получена из T, начинается либо с a, либо с c, либо является пустой строкой. В результате элемент T -> .aT [$$] говорит нам сместиться при просмотре либо ac, либо aa (что мы получили бы от a и c), либо на a$ (что мы получили бы если мы использовали продукцию T → ε, то взяли один из символов $ из обычного просмотра вперед.
В общем, следуя той же общей процедуре - используя терминал (ы) после точки, терминалы в предварительный просмотр, установленный для элемента, и символы, которые могут появляться в начале любых строк, получаемых из будущих нетерминалов - мы можем вычислить двухсимвольные предварительные просмотры, которые мы используем, чтобы определить, когда перейти. В частности, мы остались с этим :
(3)
R -> ab.T [$$]
R -> ab.T [ab]
T -> .aT [$$] // Shift on aa, ac, a$
T -> .c [$$] // Shift on c$
T -> . [$$] // Reduce on $$
T -> .aT [ab] // Shift on aa, ac
T -> .c [ab] // Shift on ca
T -> . [ab] // Reduce on ab
К счастью, здесь нет конфликтов сдвига / уменьшения, потому что каждый двухсимвольный просмотр вперед говорит нам делать что-то другое.
Взгляд за точку, чтобы определить, когда сдвигать, что-то новое для синтаксического анализа LR (2), которое появляется при синтаксическом анализе LR (k> 1), но не при анализе LR (1). При синтаксическом анализе LR (1) нам просто нужно смотреть на терминал за точкой. В LR (2) синтаксический анализ, поскольку нам нужно больше символов, чтобы определить, что делать, мы должны вычислить вторичную точку просмотра вперед для каждого элемента сдвига. В частности, просмотр с точками вперед определяется следующим образом:
В продукте A → α.tω [γ], где t - терминал, точечный просмотр вперед - это набор всех строк длиной 2, которые может появиться в начале строки, полученной из tωγ. Другими словами, продукция A → α.tω [γ] имеет точечный просмотр вперед, равный FIRST 2 (tωγ).
Имея все это в виду, мы можем построить полный анализатор LR (2) и описать действия, связанные с каждым состоянием. Общий анализатор LR (2) выглядит так:
(1)
S' -> .S [$$] // Go to 10
S -> .R [$$] // Go to 8
S -> .RS [$$] // Go to 8
R -> .abT [$$] // Shift on ab, go to (2)
R -> .abT [ab] // Shift on ab, go to (2)
(2)
R -> a.bT [$$] // Shift on ba, bc, b$, go to (3)
R -> a.bT [ab] // Shift on ba, bc, go to (3)
(3)
R -> ab.T [$$] // Go to 7
R -> ab.T [ab] // Go to 7
T -> .aT [$$] // Shift on aa, ac, a$, go to (4)
T -> .c [$$] // Shift on c$, go to (5)
T -> . [$$] // Reduce on $$
T -> .aT [ab] // Shift on aa, ac, go to (4)
T -> .c [ab] // Shift on ca, go to (5)
T -> . [ab] // Reduce on ab
(4)
T -> a.T [$$] // Go to 6
T -> a.T [ab] // Go to 6
T -> . [$$] // Reduce on $$
T -> .aT [$$] // Shift on aa, ac, a$, go to (4)
T -> .c [$$] // Shift on c$, go to (5)
T -> . [ab] // Reduce on ab
T -> .aT [ab] // Shift on aa, ac, go to (4)
T -> .c [ab] // Shift on ca, go to (5)
(5)
T -> c. [$$] // Reduce on $$
T -> c. [ab] // Reduce on ab
(6)
T -> aT. [$$] // Reduce on $$
T -> aT. [ab] // Reduce on ab
(7)
R -> abT. [$$] // Reduce on $$
R -> abT. [ab] // Reduce on ab
(8)
S -> R. [$$] // Reduce on $$
S -> R.S [$$] // Go to 9
S -> .RS [$$] // Go to 8
S -> .R [$$] // Go to 8
R -> .abT [$$] // Shift on ab, go to (2)
R -> .abT [ab] // Shift on ab, go to (2)
(9)
S -> RS. [$$] // Reduce on $$
(10)
S' -> S. [$$] // Accept on $$
Итак, теперь у нас есть синтаксический анализатор LR (2) для этой грамматики. Все, что осталось сделать, это закодировать это как таблицу действий и перехода в соответствии с тем, что мы делаем для парсера LR (1).
Как и следовало ожидать, таблица действий для синтаксического анализатора LR (2) отличается от таблицы действий для синтаксического анализатора LR (1) тем, что для нее используются опережающие просмотры, задаваемые двумя символами, а не одним символом. Это означает, что таблица действий для парсера LR (2) будет намного больше, чем для парсера LR (1). Вот как это выглядит здесь:
state | aa | ab | ac | a$ | ba | bb | bc | b$ | ca | cb | cc | c$ | $$
------+----+----+----+----+----+----+----+----+----+----+----+----+----
1 | | S | | | | | | | | | | |
------+----+----+----+----+----+----+----+----+----+----+----+----+----
2 | | | | | S | | S | S | | | | |
------+----+----+----+----+----+----+----+----+----+----+----+----+----
3 | S | R | S | S | | | | | S | | | S | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
4 | S | R | S | S | | | | | S | | | S | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
5 | | R | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
6 | | R | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
7 | | R | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
8 | | S | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
9 | | | | | | | | | | | | | R
------+----+----+----+----+----+----+----+----+----+----+----+----+----
10 | | | | | | | | | | | | | A
Как видите, каждая запись здесь просто говорит, следует ли сдвигать или уменьшать. На практике каждый элемент сокращения будет помечен, для какой продукции вы на самом деле выполняете сокращение, но, ммм, мне было лень напечатать это.
В таблице синтаксического анализа LR (1) вы Обычно я объединял эту таблицу с таблицей "goto", указывая, куда нужно go после просмотра каждого символа. Это случайное совпадение. В парсере LR (1) размер опережающего просмотра равен 1, что совпадает с тем фактом, что таблица goto сообщает, куда вы должны перейти после просмотра следующего символа. В синтаксическом анализаторе LR (2) решение о том, сдвигать или сокращать, зависит от двух символов предварительного просмотра, но выбор того, где go следующий после чтения еще одного символа ввода зависит только от одного символа. То есть, даже если у вас есть два токена просмотра вперед, чтобы решить, делать ли, вы перемещаете только один символ за раз. Это означает, что таблица перехода для парсера LR (2) очень похожа на таблицу перехода для парсера LR (0) или LR (1) и показана здесь:
state | a | b | c | $ | S | R | T
-------+-----+-----+-----+-----+-----+-----+-----
1 | 2 | | | | 10 | 8 |
-------+-----+-----+-----+-----+-----+-----+-----
2 | | 3 | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
3 | 4 | | 5 | | | | 7
-------+-----+-----+-----+-----+-----+-----+-----
4 | 4 | | 5 | | | | 6
-------+-----+-----+-----+-----+-----+-----+-----
5 | | | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
6 | | | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
7 | | | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
8 | 2 | | | | 9 | 8 |
-------+-----+-----+-----+-----+-----+-----+-----
9 | | | | | | |
-------+-----+-----+-----+-----+-----+-----+-----
10 | | | | | | |
Итак, чтобы суммируем:
- Анализатор LR (2) использует два токена просмотра вперед для каждого элемента LR. Это означает, что нам нужно работать с наборами FIRST 2 , а не с наборами FIRST, и вводит некоторую новую сложность при определении того, следует ли сдвигать или уменьшать.
- LR (2) синтаксический анализ имеет точка просмотра вперед . Для каждого элемента сдвига мы используем набор FIRST 2 , чтобы определить, какие символы могут юридически следовать за точкой, откуда мы находимся, и сдвигать любой из них.
- Действие LR (2) таблица вводится парами символов, а не отдельными символами, но таблица goto по-прежнему вводится символами.
Интересно, что если вы знаете, как построить парсер LR (2), вы можете обобщить идея построить парсер LR (k) для любого k ≥ 2. В частности, все «новые сюрпризы», которые здесь возникли, совпадают с теми, которые вы увидите для все больших и больших значений k.
На практике парсеры LR (2) редко используются из-за размера их таблиц действий и того факта, что они обычно имеют намного больше состояний, чем парсер LR (1) из-за увеличенного просмотра вперед. Но все же стоит, ИМХО, посмотреть, как они работают. Это дает вам представление о том, как анализ LR работает в более общем плане.
Надеюсь, это поможет!
Огромное спасибо @ AProgrammer за ответ на cs.stackexchange.com о просмотре с точками вперед по сравнению с просмотром элементов, который помог мне лучше понять, как работают точечные просмотры вперед и какова их цель!
Если вы хотите прочитать исходный документ о синтаксическом анализе LR (k), в котором подробно описаны все правила синтаксического анализа LR (k), ознакомьтесь с разделом "На Перевод языков слева направо »Дона Кнута.