Все существующие программы. Часть 2
Предположим мы хотим найти CFG для чисел и суммирования. Рассмотрим очень простую грамматику только с одним нетерминальным символом. Можно сказать, что выражением является либо число, либо сумма двух выражений:
X: 1 | 2 | 3 | X + X
Мы можем сделать следующий набор замен, каждый раз заменяя оставшийся крайний слева нетерминальный символ:
X
X + X
X + X + X
1 + X + X
1 + 2 + X
1 + 2 + 3
Мы также можем сделать набор замен, опять-таки, заменяя каждый раз оставшийся крайний слева нетерминальный символ:
X
X + X
1 + X <-- по другому!
1 + X + X
1 + 2 + X
1 + 2 + 3
Как интересно; у нас есть два весьма похожих, но тем не менее разных «левосторонних» выводов одинаковой последовательности терминальных символов! CFG, для которых существует наборы терминальных символов с двумя различными происхождениями, называется «неоднозначной» грамматикой (ambiguous grammar). Обычно чрезвычайно сложно корректно разобрать неоднозначную CFG, хотя мы здесь и не пытаемся этого сделать. Но неоднозначную CFG также сложно использовать и для генерации всех строк языка, поскольку иногда вы получаете одну и ту же строку более одного раза. Для наших целей было бы идеально гарантировать, что определенная строка была сгенерирована только один раз. Если CFG является однозначной, тогда мы знаем, что все возможные комбинации правил не приведут к генерации одинаковой строки дважды.
К несчастью, в общем случае проблема неоднозначности не имеет доказуемого решения. Не существует общего пути, чтобы (1) посмотреть грамматику и определить является ли она неоднозначной или (2) взять неоднозначную CFG и найти «эквивалентную» однозначную CFG. Однако не все потеряно. Существует способы доказательства того, что некоторая грамматика является однозначной, даже когда общих решений и не существует. Существует множество распространенных хитрых трюков, которые позволяют найти неоднозначные грамматики, с которыми мы обычно встречаемся в языках программирования. В нашем конкретном случае, мы можем сказать следующее:
S: N | S + N
N: 1 | 2 | 3
В таком случае левосторонним выводом для 1 + 2 + 3 будет
S
S + N
S + N + N
N + N + N
1 + N + N
1 + 2 + N
1 + 2 + 3
Я не стану доказывать, что эта грамматика является однозначной; это заведет нас в слишком далекие дебри. Просто поверьте мне на слово, эта грамматика однозначна. С этого момента мы постараемся создавать только однозначные грамматики.
В следующий раз: пустые высказывания требуют дополнительной работы.