Pull to refresh

Компиляция. 2: грамматики

Programming *
В предыдущем посте было много кода и, по некоторым мнениям, недостаточно объяснений. Будем чередовать: в этот раз будет много теории, а до практики почти не дойдёт.

Далее в посте:

  1. Магазинный автомат
  2. Формальные грамматики
  3. LR-парсинг

Магазинный автомат


В прошлый раз обозначили проблему с регулярными выражениями и постройкой по ним ДКА для разбора текста: невозможно определить, на одном ли уровне вложенности расположены в тексте скобки. При помощи регэкспов невозможно решить даже намного более узкую задачу: проверить в строке типа {*}*, равно ли количество { количеству }. Доказательство ведётся от противного: предположим, что можно создать такой регэксп. Значит, можно построить по нему ДКА, который будет отличать подходящие строки от неподходящих. Если в получившемся ДКА есть N состояний, то на строке типа {N+1 (т.е. "N+1 раз {") автомат в каком-то из состояний побывает больше одного раза («зациклится»). Значит, добавив в начало строки новые символы {, можно прогнать автомат по тому же циклу лишний раз — и он не заметит подмены. В итоге, автомат не сможет отличить подходящую строку {N+1}N+1 от неподходящей строки {N+M+1}N+1. (M — длина обнаруженного в автомате цикла; именно столько { добавляем в начало строки.)

Иными словами, ДКА не может распознавать вложенные конструкции из-за того, что у него недостаточно памяти: всё, что он помнит, — одно лишь значение от 1 до N (номер текущего состояния). Нам потребуется более ёмкий автомат, память которого сможет неограниченно расти по мере необходимости.

У автомата с магазинной памятью, кроме текущего состояния, есть стек, куда он может записывать символы. На каждом шаге автомат читает следующий входной символ, плюс верхний символ из стека. В соответствии с тройкой (текущее состояние, входной символ, символ из стека) автомат выбирает, в какое состояние перейти, и что записать в стек вместо прочитанного символа. Запись в стек необязательна: можно просто стереть оттуда прочитанный символ; так что стек во время работы может и расти, и сокращаться.

По поводу терминологии: магазинный автомат не имеет отношения к торговым автоматам в магазинах. Как ни странно, магазинный автомат назван в честь автоматных магазинов (см.рис.), являющихся классической реализацией стека: доступ возможен только к самому верхнему элементу патрону.

Теперь сможем решить исходную задачу: проверить, поровну ли в строке { и }. Читая каждую {, записываем её в стек. Читая каждую }, стираем из стека одну {.

состояние 1: считаем {
             символ стека:        {                        EOF (стек пуст)
входной символ:
      {                 записать {{, остаться в 1      записать {, остаться в 1
      }               ничего не писать, перейти в 2     строка не подходит (1)
     EOF                 строка не подходит (2)           строка подходит (3)


состояние 2: считаем }
             символ стека:        {                        EOF (стек пуст)
входной символ:
      {                  строка не подходит (4)         строка не подходит (4)
      }               ничего не писать, остаться в 2    строка не подходит (5)
     EOF                 строка не подходит (6)           строка подходит (7)
Примечания:
  1. строка начинается с }
  2. в начале строки есть несколько {, но после них нет ни одного }
  3. строка пуста
  4. после } в строке снова есть {
  5. } больше, чем { (стек закончился, а ввод нет)
  6. } меньше, чем { (ввод закончился, а стек нет)
  7. поровну { и } (стек и ввод закончились одновременно)

Кроме ёмкого автомата, нам ещё потребуется новый способ задания синтаксиса — более гибкий, чем регэкспы.

Формальные грамматики


Для определения языковых конструкций, поддерживающих произвольную вложенность, стали использовать «правила вывода», состоящие из символов («терминалов») и переменных («нетерминалов»), например для рассмотренной выше задачи вложенных скобок:
VALID: '{' VALID '}' ;
VALID: ;
Слева, до двоеточия — переменная; справа — кусок текста, который может из неё получиться, и который может содержать переменные, включая рекурсивные ссылки на определяемую переменную.

Чтобы сэкономить место, альтернативные определения одной и той же переменной можно разделять |:
VALID: '{' VALID '}' | ;

Более содержательный пример — грамматика арифметических выражений:
EXPR: NUM | EXPR OP EXPR ;
NUM: DIGIT | NUM DIGIT ;
DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
OP: '+' | '-' | '*' | '/' ;

Грамматики такого типа называются контекстно-свободными, указывая на то, что определения переменных не зависят от контекста: например, NUM всегда соответствует строчке из десятичных цифр, даже если перед числом стояло '0x'. На практике контекстно-зависимые грамматики не используются, потому что для них нет эффективных способов разбора.

Итак, в соответствии с нашей грамматикой, выражение 22+3*4-5 распознавалось бы так:
  '2'  '2'  '+' '3'  '*' '4' '-'  '5'
DIGIT DIGIT OP DIGIT OP DIGIT OP DIGIT
 NUM  DIGIT OP  NUM  OP  NUM  OP  NUM
   NUM      OP EXPR  OP  EXPR OP EXPR
    EXPR    OP EXPR  OP      EXPR
           EXPR      OP      EXPR
                    EXPR
А может быть, и так:
  '2'  '2'  '+' '3'  '*' '4' '-'  '5'
DIGIT DIGIT OP DIGIT OP DIGIT OP DIGIT
 NUM  DIGIT OP  NUM  OP  NUM  OP  NUM
   NUM      OP EXPR  OP EXPR  OP EXPR
    EXPR    OP      EXPR      OP EXPR
           EXPR               OP EXPR
                            EXPR
В первом случае, выражение распознаётся как произведение суммы слева и разности справа; во втором — в соответствии с правилами арифметики. Возможны и другие варианты, кроме двух приведённых.

Когда у одного выражения есть несколько «деревьев разбора», возникает вопрос: которое из них парсер должен выбрать?

Аналогичная проблема была и с регулярными выражениям: если применить (.+)[ ](.+) к строчке «quick brown fox», то могло бы получиться либо $1=«quick brown» и $2=«fox», либо $1=«quick» и $2=«brown fox». Про регулярные выражения договорились, что они действуют «жадно», и, читая строку слева направо, забирают в каждое под-выражение как можно больше подходящих символов. (Так что на самом деле получим «quick brown» и «fox»).

С грамматиками такой договорённости нет. Если грамматика допускает неоднозначный разбор, то это плохая, негодная грамматика, и нужно придумать другую. Например, грамматика для калькулятора торговок с рынка, который все действия выполняет слева направо, была бы такой:
EXPR: NUM | EXPR OP NUM ;
NUM: DIGIT | NUM DIGIT ;
DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
OP: '+' | '-' | '*' | '/' ;
Теперь в определении EXPR второй операнд — всегда голое число, и поэтому разбор может быть только таким:
  '2'  '2'  '+' '3'  '*' '4' '-'  '5'
DIGIT DIGIT OP DIGIT OP DIGIT OP DIGIT
 NUM  DIGIT OP  NUM  OP  NUM  OP  NUM
   NUM      OP  NUM  OP  NUM  OP  NUM
    EXPR    OP  NUM  OP  NUM  OP  NUM
           EXPR      OP  NUM  OP  NUM
                    EXPR      OP  NUM
                            EXPR

Если хотим вместо этого, чтоб соблюдался приоритет умножения над сложением, то нужно определить EXPR как сумму произведений:
EXPR: TERM | EXPR '+' TERM | EXPR '-' TERM ;
TERM: NUM | TERM '*' NUM | TERM '/' NUM ;
NUM: DIGIT | NUM DIGIT ;
DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;

'2' '2' '+' '3' '*' '4' '-' '5'
DIGIT DIGIT '+' DIGIT '*' DIGIT '-' DIGIT
NUM DIGIT '+' NUM '*' NUM '-' NUM
NUM '+' TERM '*' NUM '-' TERM
TERM '+' TERM '-' TERM
EXPR '+' TERM '-' TERM
EXPR '-' TERM
EXPR

В языках программирования похожие неоднозначности встречаются нередко, а в C++ так прямо на каждом шагу: комментаторы упомянули замечательную статью «Редкая профессия» о разработке компилятора C++ от начала до конца.
Не время углубляться в специфику, но самый простой пример — if (1) if (2) foo(); else bar(); — может истрактоваться либо как if (1) { if (2) foo(); else bar(); }, либо как if (1) { if (2) foo(); } else bar();, если составитель грамматики не позаботится запретить одну из трактовок.
Составление грамматик без неоднозначностей — важный скилл.

LR-парсинг


Как заставить магазинный автомат распознавать грамматику?
Он будет читать входную строку символ за символом, и записывать (сдвигать) прочитанные символы в стек. Как только наверху стека соберётся последовательность (символов и переменных), подходящая к правилу грамматики, автомат вытолкнет всю её из стека, и заменит на переменную, стоящую в левой части подошедшего правила (свёртка). Вся работа автомата заключается в последовательности сдвигов и свёрток.

Интересный момент: автомату на самом деле не важно, какие символы лежат в стеке. Всё равно он не может их сравнить с правилами грамматики, потому что видит только верхний; вместо этого он выбирает, какое правило применить для свёртки, по своему текущему состоянию. Стек ему нужен затем, чтобы знать, в какое состояние перейти после свёртки. Для этого он во время сдвига записывает в стек, вместе с символом, своё текущее состояние; а во время свёртки берёт из стека состояние, записанное под всеми стёртыми символами, и в зависимости от него переходит в следующее состояние.

Придирчивый хабраюзер заметит, что получается не совсем магазинный автомат: на каждом шаге из стека стирается не один элемент, а сразу несколько; и смотрим не на верхний элемент стека, а на тот, что под стёртыми. Вдобавок, во время свёртки автомат оставляет входной символ непрочитанным. Теоретически, такой «расширенный» автомат можно преобразовать к «стандартному» виду, создав кучу дополнительных состояний для очистки стека. На практике, реализация обоих вариантов совершенно аналогична: точно такие же цикл, стек и таблица переходов. Чтобы сэкономить место под таблицу переходов, пользуются «расширенным» автоматом, не раздувая зря его состояния.

Чтобы распознать последнюю нашу грамматику (арифметические выражения с правильным приоритетом операций), потребуется автомат из 11 состояний:
состояние 1:
  цифра: сдвиг, перейти в 2
состояние 2:
  удалить 1 символ из стека, записать туда DIGIT
  если состояние на стеке — 1 или 7 или 10, перейти в 3
  если состояние на стеке — 4 или 9, перейти в 5
состояние 3:
  удалить 1 символ из стека, записать туда NUM
  если состояние на стеке — 1 или 10, перейти в 4
  если состояние на стеке — 7, перейти в 9
состояние 4:
  цифра: сдвиг, перейти в 2
  иначе: удалить 1 символ из стека, записать туда TERM
         если состояние на стеке — 1, перейти в 6
         если состояние на стеке — 10, перейти в 11
состояние 5:
  удалить 2 символа из стека, записать туда NUM
  если состояние на стеке — 1, перейти в 4
  если состояние на стеке — 7, перейти в 9
состояние 6:
  '*','/': сдвиг, перейти в 7
  иначе: удалить 1 символ из стека, записать туда EXPR
         если состояние на стеке — 1, перейти в 8
состояние 7:
  цифра: сдвиг, перейти в 2
состояние 8:
  EOF: выражение распознано успешно
  '+','-': сдвиг, перейти в 10
состояние 9:
  цифра: сдвиг, перейти в 2
  иначе: удалить 3 символа из стека, записать туда TERM
         если состояние на стеке — 1, перейти в 6
         если состояние на стеке — 10, перейти в 11
состояние 10: сдвиг EXPR: EXPR '+' TERM  либо сдвиг EXPR: EXPR '+' TERM
  цифра: сдвиг, перейти в 2
состояние 11:
  '*','/': сдвиг, перейти в 7
  иначе: удалить 3 символа из стека, записать туда EXPR
         если состояние на стеке — 1, перейти в 8

Не будем останавливаться на том, откуда этот автомат взялся; предположим, его принесло нам НЛО.
Лучше посмотрим, как он работает: пропустим через него всё то же выражение 22+3*4-5:
состояние 1,  вход "22+3*4-5",  стек пуст
* цифра: сдвиг, перейти в 2
состояние 2,  вход "2+3*4-5",   стек '2',(1)
* удалить 1 символ из стека, записать туда DIGIT, перейти в 3
состояние 3,  вход "2+3*4-5",   стек DIGIT,(1)
* удалить 1 символ из стека, записать туда NUM, перейти в 4
состояние 4,  вход "2+3*4-5",   стек NUM,(1)
* цифра: сдвиг, перейти в 2
состояние 2,  вход "+3*4-5",    стек '2',(4),NUM,(1)
* удалить 1 символ из стека, записать туда DIGIT, перейти в 5
состояние 5,  вход "+3*4-5",    стек DIGIT,(4),NUM,(1)
* удалить 2 символа из стека, записать туда NUM, перейти в 4
состояние 4,  вход "+3*4-5",    стек NUM,(1)
* удалить 1 символ из стека, записать туда TERM, перейти в 6
состояние 6,  вход "+3*4-5",    стек TERM,(1)
* удалить 1 символ из стека, записать туда EXPR, перейти в 8
состояние 8,  вход "+3*4-5",    стек EXPR,(1)
* '+': сдвиг, перейти в 10
состояние 10, вход "3*4-5",     стек '+',(8),EXPR,(1)
* цифра: сдвиг, перейти в 2
состояние 2,  вход "*4-5",      стек '3',(10),'+',(8),EXPR,(1)
* удалить 1 символ из стека, записать туда DIGIT, перейти в 3
состояние 3,  вход "*4-5",      стек DIGIT,(10),'+',(8),EXPR,(1)
* удалить 1 символ из стека, записать туда NUM, перейти в 4
состояние 4,  вход "*4-5",      стек NUM,(10),'+',(8),EXPR,(1)
* удалить 1 символ из стека, записать туда TERM, перейти в 11
состояние 11, вход "*4-5",      стек TERM,(10),'+',(8),EXPR,(1)
* '*': сдвиг, перейти в 7
состояние 7,  вход "4-5",       стек '*',(11),TERM,(10),'+',(8),EXPR,(1)
* цифра: сдвиг, перейти в 2
состояние 2,  вход "-5",        стек '4',(7),'*',(11),TERM,(10),'+',(8),EXPR,(1)
* удалить 1 символ из стека, записать туда DIGIT, перейти в 3
состояние 3,  вход "-5",        стек DIGIT,(7),'*',(11),TERM,(10),'+',(8),EXPR,(1)
* удалить 1 символ из стека, записать туда NUM, перейти в 9
состояние 9,  вход "-5",        стек NUM,(7),'*',(11),TERM,(10),'+',(8),EXPR,(1)
* удалить 3 символа из стека, записать туда TERM, перейти в 11
состояние 11, вход "-5",        стек TERM,(10),'+',(8),EXPR,(1)
* удалить 3 символа из стека, записать туда EXPR, перейти в 8
состояние 8,  вход "-5",        стек EXPR,(1)
* '-': сдвиг, перейти в 10
состояние 10, вход "5",         стек '-',(8),EXPR,(1)
* цифра: сдвиг, перейти в 2
состояние 2,  вход пуст,        стек '5',(10),'-',(8),EXPR,(1)
* удалить 1 символ из стека, записать туда DIGIT, перейти в 3
состояние 3,  вход пуст,        стек DIGIT,(10),'-',(8),EXPR,(1)
* удалить 1 символ из стека, записать туда NUM, перейти в 4
состояние 4,  вход пуст,        стек NUM,(10),'-',(8),EXPR,(1)
* удалить 1 символ из стека, записать туда TERM, перейти в 11
состояние 11, вход пуст,        стек TERM,(10),'-',(8),EXPR,(1)
* удалить 3 символа из стека, записать туда EXPR, перейти в 8
состояние 8,  вход пуст,        стек EXPR,(1)
* EOF: выражение распознано успешно

По сути, наш автомат определяет, является ли входная строка правильным арифметическим выражением. Если нет, то в одном из состояний не окажется действия, подходящего очередному входному символу; и тогда автомат сообщит о синтаксической ошибке.
Можем при помощи того же автомата и вычислять выражения: в каждом символе в стеке будем хранить его математическое значение; при свёртке, вычислим значение нового символа на основании удаляемых из стека.
Получится продвинутый калькулятор, который учитывает приоритет операций:
состояние 1,  вход "22+3*4-5",  стек пуст
* цифра: сдвиг, перейти в 2
состояние 2,  вход "2+3*4-5",   стек '2',(1)
* удалить '2' из стека, записать туда DIGIT=2, перейти в 3
состояние 3,  вход "2+3*4-5",   стек DIGIT=2,(1)
* удалить DIGIT=2 из стека, записать туда NUM=2, перейти в 4
состояние 4,  вход "2+3*4-5",   стек NUM=2,(1)
* цифра: сдвиг, перейти в 2
состояние 2,  вход "+3*4-5",    стек '2',(4),NUM=2,(1)
* удалить '2' символ из стека, записать туда DIGIT=2, перейти в 5
состояние 5,  вход "+3*4-5",    стек DIGIT=2,(4),NUM=2,(1)
* удалить DIGIT=2,NUM=2 из стека, записать туда NUM=22, перейти в 4
состояние 4,  вход "+3*4-5",    стек NUM=22,(1)
* удалить NUM=22 из стека, записать туда TERM=22, перейти в 6
состояние 6,  вход "+3*4-5",    стек TERM,(1)
* удалить TERM=22 из стека, записать туда EXPR=22, перейти в 8
состояние 8,  вход "+3*4-5",    стек EXPR=22,(1)
* '+': сдвиг, перейти в 10
состояние 10, вход "3*4-5",     стек '+',(8),EXPR=22,(1)
* цифра: сдвиг, перейти в 2
состояние 2,  вход "*4-5",      стек '3',(10),'+',(8),EXPR=22,(1)
* удалить '3' из стека, записать туда DIGIT=3, перейти в 3
состояние 3,  вход "*4-5",      стек DIGIT=3,(10),'+',(8),EXPR=22,(1)
* удалить DIGIT=3 из стека, записать туда NUM=3, перейти в 4
состояние 4,  вход "*4-5",      стек NUM=3,(10),'+',(8),EXPR=22,(1)
* удалить NUM=3 символ из стека, записать туда TERM=3, перейти в 11
состояние 11, вход "*4-5",      стек TERM=3,(10),'+',(8),EXPR=22,(1)
* '*': сдвиг, перейти в 7
состояние 7,  вход "4-5",       стек '*',(11),TERM=3,(10),'+',(8),EXPR=22,(1)
* цифра: сдвиг, перейти в 2
состояние 2,  вход "-5",        стек '4',(7),'*',(11),TERM=3,(10),'+',(8),EXPR=22,(1)
* удалить '4' из стека, записать туда DIGIT=4, перейти в 3
состояние 3,  вход "-5",        стек DIGIT=4,(7),'*',(11),TERM=3,(10),'+',(8),EXPR=22,(1)
* удалить DIGIT=4 символ из стека, записать туда NUM=4, перейти в 9
состояние 9,  вход "-5",        стек NUM=4,(7),'*',(11),TERM=3,(10),'+',(8),EXPR=22,(1)
* удалить NUM=4,'*',TERM=3 из стека, записать туда TERM=12, перейти в 11
состояние 11, вход "-5",        стек TERM=12,(10),'+',(8),EXPR=22,(1)
* удалить TERM=12,'+',EXPR=22 из стека, записать туда EXPR=34, перейти в 8
состояние 8,  вход "-5",        стек EXPR=34,(1)
* '-': сдвиг, перейти в 10
состояние 10, вход "5",         стек '-',(8),EXPR=34,(1)
* цифра: сдвиг, перейти в 2
состояние 2,  вход пуст,        стек '5',(10),'-',(8),EXPR=34,(1)
* удалить '5' из стека, записать туда DIGIT=5, перейти в 3
состояние 3,  вход пуст,        стек DIGIT=5,(10),'-',(8),EXPR=34,(1)
* удалить DIGIT=5 из стека, записать туда NUM=5, перейти в 4
состояние 4,  вход пуст,        стек NUM=5,(10),'-',(8),EXPR=34,(1)
* удалить NUM=5 из стека, записать туда TERM=5, перейти в 11
состояние 11, вход пуст,        стек TERM=5,(10),'-',(8),EXPR=34,(1)
* удалить TERM=5,'-',EXPR=34 из стека, записать туда EXPR=29, перейти в 8
состояние 8,  вход пуст,        стек EXPR=29,(1)
* EOF: выражение распознано успешно, значение =29

Парсер в реальном компиляторе устроен похоже, только там в каждой свёртке не вычисляется выражение, а генерируется соответствующий код.

Описанный способ парсинга называется восходящим: начинаем с распознавания мельчайших конструкций, и, соединяя их воедино, получаем всё большие. Есть и противоположный, нисходящий подход: начинаем с конструкции «весь текст», и дробим её, распознавая всё более мелкие подконструкции. Между сторонниками двух подходов, как выяснилось, ведутся вялые холиворы: каждая сторона считает, что именно её подход естественнее, ближе к распознаванию синтаксиса человеком, и поэтому проще в отладке.

В следующий раз познакомимся с бизоном, который по грамматике сам строит распознающий LR-автомат, и тогда сможем скомпилировать наш расчудесный калькулятор.
Tags:
Hubs:
Total votes 56: ↑51 and ↓5 +46
Views 34K
Comments Comments 21