1) Демонстрация неоднозначности

Грамматика $исходная$ S -> S + S | S * S | a | $S$

Строка-пример: a + a * a

Два различных дерева разбора.

Вариант A $плюснаверхнемуровне:a+(a\ast a)$:

S
/|\
S + S
| /|\
a S * S
| |
a a

Соответствующий вывод:
S ⇒ S + S ⇒ a + S ⇒ a + $S<em>S$ ⇒ a + $a</em>a$

Вариант B $звёздочканаверхнемуровне:(a+a)\ast a$:

S
/|\
S * S
/|\ |
S + S a
| | |
a a a

Вывод:
S ⇒ S S ⇒ $S+S$ S ⇒ $a+a$ * a

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

2) Неамбигуализированная грамматика с приоритетами и левой ассоциативностью

Требование: * имеет более высокий приоритет, + — ниже; обе операции левосторонние.

Классическое неамбигуизированное правило:

E -> E + T | T
T -> T * F | F
F -> a | $E$

Здесь:

T соответствует произведениям $болеевысокийприоритет$,E — суммам $нижнийприоритет$,левая рекурсия E -> E + T и T -> T * F задаёт левую ассоциативность.

Эквивалентная форма, удобная для LL$1$ $убираемлевуюрекурсию$:

E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> a | $E$

3) Почему это однозначно и задаёт заданные приоритеты/ассоциативности

В этой грамматике операции образуются в поддеревьях T, которые находятся ниже по иерархии, чем E, поэтому связывается сильнее, чем +. Для строки a + a a единственный допустимый разбор по этой грамматике — E -> T E' с T->F и правой частью T' дающей a$a$ — то есть a + $a\ast a$.Левая рекурсия E -> E + T гарантирует, что последовательность a + a + a разобьётся как $a+a$ + a $леваяассоциативность$, а не как a + $a+a$.

4) Описание алгоритма синтаксического анализатора

Вариант A — LL$1$, рекурсивный нисходящий предиктивный парсер

Используем LL$1$-форму $E,E^{\prime },T,T^{\prime },F$.Построить таблицу предсказания по FIRST/FOLLOW (коротко: FIRST(+ T E') = '+', FIRST(T)= {'a','('}, FIRST(E') = {'+','ε'}, и т.д.). Эта грамматика является LL(1).Реализовать функции (псевдокод):

function parseE():
parseT()
parseEprime()

function parseEprime():
if current_token == '+':
consume('+')
parseT()
parseEprime()
else
// ε: вернуть

function parseT():
parseF()
parseTprime()

function parseTprime():
if current_token == '':
consume('')
parseF()
parseTprime()
else
// ε: вернуть

function parseF():
if current_token == 'a':
consume('a')
else if current_token == '(':
consume('(')
parseE()
expect(')') // consume ')' или ошибка
else
error()

Этот парсер читается слева направо, использует прогноз по одному символу (LL(1)). Постфикс вызовов гарантирует, что парсер отражает приоритеты: внутри E мы сначала распознаём T (вся цепочка * и F), затем уже разрешаем +.

Вариант B — LR (shift-reduce, LALR(1)/LR(1))

Можно строить стандартный LR(1)/LALR(1)-парсер для неамбигуализированной грамматики (E->E+T|T, T->T*F|F, F->a|(E)).Алгоритм (общая схема):
Построить множество состояний автомата LR(1) (канонические множества LR(1)-шпилек/пунктов) и таблицы action/goto.Парсер хранит стек состояний; на вход подаётся поток токенов.На каждом шаге берётся текущее состояние s (вершина стека) и текущий токен a:если action[s,a] = "shift t": поместить токен и состояние t в стек, прочитать следующий токен;если action[s,a] = "reduce A -> β": снять 2*|β| элементов со стека (символы и состояния), найти новое состояние s' = top(stack), поместить A и goto[s',A] в стек;если action[s,a] = "accept": успешно завершить;иначе — синтаксическая ошибка.Для нашей грамматики таблицы action/goto будут однозначными (без конфликта shift/reduce) — она принадлежит к классу LR(1) (и обычно к LALR(1)), поэтому парсер корректно обрабатывает приоритеты, заданные структурой грамматики.

Пример шагов (LR shift/reduce) для входа a + a * a (схематично):

shift 'a' ; reduce F->a ; reduce T->F ; (в зависимости от состояний можно сразу редьюсить) ; далее shift '+' ; shift 'a' ; shift '' ; shift 'a' ; reduce F->a ; reduce T->T F ; reduce E->E + T ; accept.
Точные состояния и действия зависят от построенной таблицы.

Резюме:

Исходная грамматика неоднозначна (пример a+a*a даёт два дерева).Неамбигуизированная версия с требуемыми приоритетами и левой ассоциативностью — стандартная E/T/F-иерархия:
E -> E + T | T ; T -> T F | F ; F -> a | ( E )
или LL(1)-эквивалент:
E->T E' ; E'-> + T E' | ε ; T->F T' ; T'-> F T' | ε ; F-> a | (E)Для неё можно реализовать либо предиктивный LL(1)-парсер (рекурсивный нисходящий), либо стандартный LR(1)/LALR(1) shift-reduce парсер; оба разбора однозначны и соблюдают требуемые приоритеты и ассоциативность.