Я смотрю на следующую грамматику и считаю ее неоднозначной в строке 3, но не уверен.
<SL> → <S>
<SL> → <SL> <S>
<S> → i <B> <S> e <S>
<S> → i <B> <S>
<S> → x
<S> → y
<B> → 5
<B> → 13
Я нашел эту строку xi13yi5xeyx Я считаю, что генерирует два разных дерева синтаксического анализа, но я не уверен, что я делаю это неправильно.
Может ли кто-нибудь проверить мои выводы?
Да, ваша грамматика неоднозначна!
Вы не упомянули, но я думаю, что <SL> можно начать
Используя ваши правила грамматики, мы можем нарисовать более одного дерева синтаксического анализа (два) для записи i5i5yey следующим образом:
<SL> <SL>
| |
<S> <S>
/ /|\ \ / | \
/ / | \ \ / | \
/ / | \ \ / | \
/ / | \ \ i <B> <S>
/ | | | \ | / /|\ \
i <B> <S> e <S> 5 / / | \ \
/ / | \ | / / | \ \
/ / | \ y / / | \ \
5 i <B> <S> / | | | \
| | i <B> <S> e <S>
5 y | | |
5 y y
Структура обоих деревьев синтаксического анализа отличается, поскольку грамматика является неоднозначной грамматикой!
Вы можете расширить приведенную выше диаграмму, чтобы сгенерировать строку дерева xi13yi5xeyx (я оставляю это как упражнение для вас)
Важно то, что язык, генерируемый этой грамматикой, является не двусмысленным языком. И для этого можно написать эквивалентную однозначную грамматику. грамматика, которая всегда генерирует уникальное дерево для каждой строки на языке грамматики.
СОВЕТ: написать однозначную грамматику.
Грамматика очень похожа на грамматику для if loop в языке C (обратите внимание, что разные языки имеют другой синтаксис для if loop). и это решено почти во всех книгах по проектированию компиляторов.
Разрешение общей двусмысленности Else/If-Else
Ссылка: Книга "Принципы, методы и инструменты компиляторов" Ахо-Уллмана Раздел 4.5, конфликты во время синтаксического анализа Shift and-Reduce.
