Грамматика Г это четвёрка <Н, Т, С, П>, где Н - это множество нетерминальных символов, Т - это множество терминальных символов, С - это стартовый символ, П - это множество правил вывода.

Нетерминальные символы Н = {н1,н2,н3,н4,н5}

Запишем терминалы для калькулятора Т={т₁,т₂,т₃,...,т₇}:
т₁ = '+'
т₂ = '-'
т₃ = '*'
т₄ = '/'
т₅ = '('
т₆ = ')'
т₇ = '1'

Стартовый символ С = { н₁ } (тут есть варианты, стартовый символ может быть один, а может быть несколько, если алгоритм типа CYK)

Запишем правила вывода для калькулятора П = {п₁,п₂,п₃,...,п₁₄}, где
п₁: н₁ -> н₂
п₂: н₁ -> н₃
п₃: н₂ -> н₄
п₄: н₂ -> н₄ н₅
п₅: н₃ -> т₁ н₂
п₆: н₃ -> т₂ н₂
п₇: н₃ -> т₁ н₂ н₃
п₈: н₃ -> т₂ н₂ н₃
п₉: н₄ -> т₃ н₅
п₁₀: н₄ -> т₄ н₅
п₁₁: н₄ -> т₃ н₅ н₄
п₁₂: н₄ -> т₄ н₅ н₄
п₁₃: н₅ -> т₅ н₁ т₆
п₁₄: н₅ -> т₇

Читаем алгоритм 5.3 с этой страницы - https://studfiles.net/preview/4599551/page:11/

расширенный МП-автомат А это семёрка <Т, Ш, М, Х, сcа, Ф, Д>, где
Т - это множество символов входного алфавита
Ш - это символы, которые могут встречаться на стеке (терминалы и нетерминалы из грамматики выше, всего 7 + 14 = 21)
М - множество состояний автомата
Х - функция переходов, которая по текущей ситуации {м, т, ш*} выдаёт следующее состояние <м', ш'>
      (расширенным этот автомат является, потому что он в стеке проверяет наличие цепочки символов стека, а не только одного)
сcа - стартовое состояние автомата
Ф - множество заключительных/конечных состояний автомата
Д - начальный символ в стеке

Состояний у автомата будет два: М = {р, з} - рабочее и завершающее

Функция переходов проверяет,
не находится ли на стеке правая часть какого-нибудь правила (если да, то производит свёртку)
если на стеке пара <Д, С> и символы закончились, то переходит в конечное состояние,
иначе кладёт терминал на стек и удаляет терминал из входного потока (выполняет сдвиг).

В этом алгоритме всё прекрасно, кроме одного - как автомат считать результат выражения будет - не описано.
мы пока предположим, что во время свёртки автомат выводит символы в выходной поток, они там оказываются в инверсной польской записи, что позволяет потом провести вычисления (но не всё тут так просто из-за унарных плюса и минуса).

https://en.wikipedia.org/wiki/LR_parser … tween_them

Ситуация - это Earley Item, то есть запись некоего правила с точкой (Earley Dot = •) внутри него

Группа ситуаций - несколько ситуаций, по каким-то причинам объединённых в одну группу.

Итак, составим список групп ситуаций (он же будет списком состояний ДКА).

Состояние {1}
$accept -> • н₁ $кон
+ н₁ -> • н₂
+ н₁ -> • н₃
+ н₂ -> • н₄
+ н₂ -> • н₂ т₁ н₄
+ н₂ -> • н₂ т₂ н₄
+ н₃ -> • н₅
+ н₃ -> • н₃ т₁ н₄
+ н₃ -> • н₃ т₂ н₄
+ н₄ -> • н₆
+ н₄ -> • н₄ т₃ н₆
+ н₄ -> • н₄ т₄ н₆
+ н₅ -> • т₂ н₆
+ н₅ -> • н₅ т₃ н₆
+ н₅ -> • н₅ т₄ н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₂{2}, т₅{3}, т₇{4}, н₁{5}, н₂{6}, н₃{7}, н₄{8}, н₅{9}, н₆{10}

Состояние {2}
н₅ -> т₂ • н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₅{3}, т₇{4}, н₆{11}

Состояние {3}
н₆ -> т₅ • н₁ т₆
+ н₁ -> • н₂
+ н₁ -> • н₃
+ н₂ -> • н₄
+ н₂ -> • н₂ т₁ н₄
+ н₂ -> • н₂ т₂ н₄
+ н₃ -> • н₅
+ н₃ -> • н₃ т₁ н₄
+ н₃ -> • н₃ т₂ н₄
+ н₄ -> • н₆
+ н₄ -> • н₄ т₃ н₆
+ н₄ -> • н₄ т₄ н₆
+ н₅ -> • т₂ н₆
+ н₅ -> • н₅ т₃ н₆
+ н₅ -> • н₅ т₄ н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₂{2}, т₅{3}, т₇{4}, н₁{12}, н₂{6}, н₃{7}, н₄{8}, н₅{9}, н₆{10}

Состояние {4}
н₆ -> т₇ •

Состояние {5}
$accept -> н₁ • $кон

Состояние {6}
н₁ -> н₂ •
н₂ -> н₂ • т₁ н₄
н₂ -> н₂ • т₂ н₄
Следующие символы: т₁{14}, т₂{15}

Состояние {7}
н₁ -> н₃ •
н₃ -> н₃ • т₁ н₄
н₃ -> н₃ • т₂ н₄
Следующие символы: т₁{22}, т₂{23}

Состояние {8}
н₂ -> н₄ •
н₄ -> н₄ • т₃ н₆
н₄ -> н₄ • т₄ н₆
Следующие символы: т₃{17}, т₄{18}

Состояние {9}
н₃ -> н₅ •
н₅ -> н₅ • т₃ н₆
н₅ -> н₅ • т₄ н₆
Следующие символы: т₃{26}, т₄{27}

Состояние {10}
н₄ -> н₆ •

Состояние {11}
н₅ -> т₂ н₆ •

Состояние {12}
н₆ -> т₅ н₁ • т₆
Следующие символы: т₆{13}

Состояние {13}
н₆ -> т₅ н₁ т₆ •

Состояние {14}
н₂ -> н₂ т₁ • н₄
+ н₄ -> • н₆
+ н₄ -> • н₄ т₃ н₆
+ н₄ -> • н₄ т₄ н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₅{3}, т₇{4}, н₄{16}, н₆{10}

Состояние {15}
н₂ -> н₂ т₂ • н₄
+ н₄ -> • н₆
+ н₄ -> • н₄ т₃ н₆
+ н₄ -> • н₄ т₄ н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₅{3}, т₇{4}, н₄{21}, н₆{10}

Состояние {16}
н₂ -> н₂ т₁ н₄ •
н₄ -> н₄ • т₃ н₆
н₄ -> н₄ • т₄ н₆
Следующие символы: т₃{17}, т₄{18}

Состояние {17}
н₄ -> н₄ т₃ • н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₅{3}, т₇{4}, н₆{19}

Состояние {18}
н₄ -> н₄ т₄ • н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₅{3}, т₇{4}, н₆{20}

Состояние {19}
н₄ -> н₄ т₃ н₆ •

Состояние {20}
н₄ -> н₄ т₄ н₆ •

Состояние {21}
н₂ -> н₂ т₂ н₄ •
н₄ -> н₄ • т₃ н₆
н₄ -> н₄ • т₄ н₆
Следующие символы: т₃{17}, т₄{18}

Состояние {22}
н₃ -> н₃ т₁ • н₄
+ н₄ -> • н₆
+ н₄ -> • н₄ т₃ н₆
+ н₄ -> • н₄ т₄ н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₅{3}, т₇{4}, н₄{24}, н₆{10}

Состояние {23}
н₃ -> н₃ т₂ • н₄
+ н₄ -> • н₆
+ н₄ -> • н₄ т₃ н₆
+ н₄ -> • н₄ т₄ н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₅{3}, т₇{4}, н₄{25}, н₆{10}

Состояние {24}
н₃ -> н₃ т₁ н₄ •
н₄ -> н₄ • т₃ н₆
н₄ -> н₄ • т₄ н₆
Следующие символы: т₃{17}, т₄{18}

Состояние {25}
н₃ -> н₃ т₂ н₄ •
н₄ -> н₄ • т₃ н₆
н₄ -> н₄ • т₄ н₆
Следующие символы: т₃{17}, т₄{18}

Состояние {26}
н₅ -> н₅ т₃ • н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₅{3}, т₇{4}, н₆{28}

Состояние {27}
н₅ -> н₅ т₄ • н₆
+ н₆ -> • т₇
+ н₆ -> • т₅ н₁ т₆
Следующие символы: т₅{3}, т₇{4}, н₆{29}

Состояние {28}
н₅ -> н₅ т₃ н₆ •

Состояние {29}
н₅ -> н₅ т₄ н₆ •

Теперь можно составить пару таблиц (состояния x терминальные символы, состояния x нетерминалы)  и начать рубить код на КуМир'е

http://ict.edu.ru/ft/005128/ch7.pdf, страница 5

Отредактировано Лис (2017-09-09 10:51:22)

В этой таблице мне не ясно, когда происходит свёртка для бинарных плюсов и минусов.

Состояние {6}
н1 -> н2 •
н2 -> н2 • т1 н4
н2 -> н2 • т2 н4
Следующие символы: т1{14}, т2{15}

Глядя на это состояние можно было бы предположить, что тут то-ли свёртка, то-ли сдвиг.

https://en.wikipedia.org/wiki/Simple_LR_parser
"A grammar that has no shift/reduce or reduce/reduce conflicts when using follow sets is called an SLR grammar"
"If a grammar has table conflicts when using SLR follow sets, but is conflict-free when using LALR follow sets, it is called a LALR grammar."

раз конфликты есть, значит эта грамматика не SLR, переходим к следующему алгоритму.

https://en.wikipedia.org/wiki/LALR_parser
   описания смысла алгоритма на той странице нет, но есть ссылка - https://web.cs.dal.ca/~sjackson/lalr1.html
   для этой грамматики нужно построить множества (начал/концов) и другие таблицы

https://ru.wikipedia.org/wiki/LALR(1)
   На русской станице википедии есть удобочитаемое объяснение смысла алгоритма

Пусть есть грамматика, не разбираемая из-за конфликтов сдвиг-свертка или свертка-свертка по алгоритму SLR(1).

В этом случае грамматика преобразуется следующим образом:

- ищется нетерминал, на котором возникла вызвавшая конфликт свертка. Обозначим его A.
- вводятся новые нетерминалы A1, A2, …, An, по одному на каждое появление A в правых частях правил.
- везде в правых частях правил A заменяется на соответствующее Ak.
- набор правил с A в левой части повторяется n раз по разу для каждого Ak.
- правила с A в левой части удаляются, тем самым полностью удаляя A из грамматики.

Для преобразованной грамматики (она изоморфна исходной) повторяется попытка построения SLR(1) таблицы разбора.

Действие основано на том, что Follow(A) есть объединение всех Follow(Ak). В каждом конкретном состоянии новая грамматика имеет уже не A, а одно из Ak, то есть множество Follow для данного состояния имеет меньше элементов, чем для A в исходной грамматике.

Это приводит к тому, что для LALR(1) совершается меньше попыток поставить «приведение» в клеточку таблицы разбора, что уменьшает риск возникновения конфликтов с приведениями, иногда вовсе избавляет от них и делает грамматику, не разбираемую по SLR(1), разбираемой после преобразования.

К гадалке не ходить - в нашем случае это списки. Поэтому можно попробовать переделать второй вариант грамматики в третий.
Но применение в лоб русского описания алгоритма не даёт годного результата,
т.к. хотя конфликты сдвиг/свёртка пропадают, зато появляются конфликты свёртка/свёртка.

Происходит это так:
Преобразуемая грамматика-пример.
н1 -> н2
н2 -> н2 т1 т7
н2 -> т7

После преобразования:
н1 -> н2a
н2a -> н2b т1 т7
н2a -> т7
н2b -> н2b т1 т7
н2b -> т7

и всё бы хорошо, только
н2a -> т7
н2b -> т7
дают конфликт свёртка-свёртка...

Вывод: прийдётся всё-таки разбираться в оригинальной работе...

Отредактировано Лис (2017-09-08 09:20:49)

http://www.larc.usp.br/~pbarreto/LR.pdf

2003, Paulo S. L. M. Barreto, "An Efficient LALR(1) and LR(1) Lookahead Set Algorithm," technical report.
1991, H. Anzai. Almost boolean algebraic computation of LALR(1) look-ahead set. Journal of Information Processing, 14(1):1–15.
  (текст не нашел)
1986, Ives.  Unifying  view  of  recent LALR (1)  lookahead  set  algorithms. SIGPLAN  Notices,  21(7):131–135
  (если бы у нас была подписка на ACM, то текст можно было бы прочитать там, в открытом интернете я его не нашел)
1985, Park, Choe, Chang, A New Analysis of LALR Formalisms
1982, DeRemer,  Pennello.  Efficient  computation  of LALR(1)  look-ahead  sets. ACM  Transactions  on Programming Languages and Systems, 4(4):615–649,

учитаться можно...

Вот тут вроде понятно расписано, как вычисляется LOOKAHEAD для каждого правила вывода. Надо будет как-нибудь при случае попробовать...

Отредактировано Лис (2017-09-08 22:59:57)