На форумах можно увидеть темы из разряда «Каким я вижу свой идеальный язык программирвоания». При этом создаются такие грамматики, которые анализатор никогда не сможет преобразовать в код. Под катом несколько опасностей, которые подстерегают разработчика нового понятного, изящного, гибкого языка программирования.
Начнем с определения. Грамматика — описание структуры языка. Например, грамматика для выражений, состоящих из цифр и знака плюс:
list -> list + digit
list -> digit
digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Пример: 9+5
Такая грамматика однозначная. Это значит, что, получив на входе определенное выражение(9+5+7), мы можем построить только одно дерево разбора данного выражения. Т е выражение 9+5+7 можно трактовать только как (9 + 5) + 7, а не 9 + (5 + 7) или как-то еще. Есть несколько видов неоднозначностей в грамматике.
1. Неоднозначность приоритетов и ассоциативности.
Возьмем простой пример неоднозначной грамматики:
E -> E+E | E*E | (E) | id
id — это просто цифра. Такая грамматика задает выражения вида: (9 + 5) * 3 или 3 * 4 + 7. Но что будет, если подать на вход выражение 1 + 2 * 3? В итоге мы получим (1 + 2) * 3 = 3 * 3 = 9. Решением данной проблемы является назначение приоритетов:
E -> E+T | T
T -> T*F | F
F -> (E) | id
Такая же ситуация с ассоциативностью. Возьмем выражение 1+2+3+4.
При грамматике с пунктом list -> list + digit мы получим разбор ((1 + 2) + 3) + 4, а при list -> digit + list мы получим разбор 1 + (2 + (3 + 4)).
2. Неоднозначность «кочующего» else
Иммется грамматика:
stmt -> if expr then stmt else stmt
| if expr then stmt
| other
Она просто раскладывает условия if-then-else. Эта грамматика неоднозначная, т. к. возможна такая запись:
if expr1 then if expr2 then smth1 else smth2.
Проблема в том, что анализатор не сможет решить, относится else к первому условию if или ко второму. Конечно, это решается расстановкой скобок:
if expr1 then {if expr2 then smth1 else smth2}
но такое возможно не всегда. Данная неоднозначность может проявится и в других конструкциях Вашего языка. Принято, что else относится к последнему then. Решение:
stmt -> matched_stmt
| unmathced_stmt
matched_stmt -> if expr then matched_stmt else matched_stmt
| other
unmathced_stmt -> if expr then stmt
| if expr then matched_stmt else unmathced_stmt
Смысл грамматики в том, что инструкция между then и else должна быть «сбалансированной»(matched), т. е не должна оканчиваться на then без соответствующего else.
3. Неоднозначность особых продукций частных случаев.
Есть неоднозначная грамматика:
E -> E func1 E func2 E
E -> E func1 E
E -> E func2 E
E -> (E)
e -> c
c — какое-либо число. В итоге имеем 2 функции, что-то делающие с числами, а также возможность расставить скобки, причем случай с последовательным вычислением func1 и func2 рассматривается как особый(возможно, там вступают в силу какие-то особые правила). Конфликт возникнет при попытке разобрать строчку:
5 func1 7 func2 9
Анализатор не сможет выбрать между E -> E func1 E func2 E и E -> E func1 E после считывания числа 7. Выход такой же, как и в пункте 1.
Ввод дополнительных переменных — не единственный способ решения данных проблем. Можно с помощью анализатора создать таблицу анализа, а потом в ней вручную проставить приоритеты для разрешения неоднозначностей, правда при большой таблице(у Pascal таблица вроде состояла из 100 000 строк) это потребует очень много времени и внимания. Я описал очень маленькую группу проблем, возникающих при написании грамматики собственного языка, не касаясь темы LL- и LR-анализаторов, левой/правой рекурсии и т. д. Пример избавления от левой рекурсии здесь.
Источники:
Альфред Ахо, Рави Сети, Джеффри Ульман «Компиляторы: принципы, технологии, инструменты»
Автор: Ramires
