Еще раз про разбор выражений методом рекурсивного спуска

[CoolCmd]

а это для тех, кому на JS самому писать разбор лениво: https://pegjs.org/online

[sshikov]

>формулами Бекуса-Наура
Вообще-то, они отродясь были формами.

[usharik]

Спасибо, поправлю.

[sshikov]

Воообще, мне кажется большинство проблем непонимания этой темы — от того, что нужно вначале немного почитать теорию. Без привязки к конкретному языку и реализации.

А дальше уже скажем LL(1) парсер уже пишется на коленке в 30 строчек, т.е. меньше чем у вас тут, плюс таблица, автоматически генерируемая на базе грамматики (я конечно упрощаю, потому что написанная на коленке грамматика скорее всего окажется не LL(1)).

И примерно так же легко пишется PEG парсер. Для большинства простых задач, если мы не ставим себе цель написать компилятор реального языка, этого будет более чем достаточно.

[usharik]

Вопрос в том, как это изложить в простой и доступной форме с максимальным акцентом на практическое применение. Может книжку или online-курс посоветуете?

[sshikov]

Ну, про PEG в принципе примеры вполне вменяемые — тот же Parboiled взять, там все более чем доступно (при условии, что грамматику мы читать уже умеем). Вообще PEG идеологически близок к регуляркам, поэтому понимается обычно легко.

Что до книжки, то я учился на старой-старой книжке Люис, Розенкранц и Стирнз, ее в принципе можно найти в виде djvu. Это наверное не самая лучшая, но мне понравилась. Она довольно близка к практике — хотя исходя из года написания ждать примеров на Java в ней не стоит (это 1976 год, не помню уж, оригинал это или перевод тогда издан).

[YuriiSig]

Могу посоветовать книгу попроще, правда, на английском: Seth D. Bergmann Compiler design: theory, tools, and examples

[Deosis]

Применим первое предложение несколько раз

E(2+3*(4-5)+6-7) -> 
T(2) + E(3*(4-5)+6-7) -> 
T(2) + T(3*(4-5)) + E(6-7) -> 
T(2) + T(3*(4-5)) + T(6) - T(7)

Что мешает применить первое правило ещё раз и получить?
T(2) + T(3*(4) - T(5)) + T(6) - T(7)
Для тех, кто первый раз сталкивается с разбором, это будет совсем неочевидно.

[usharik]

Можете чуть подробней?

[Deosis]

T('2') + E('3*(4-5)+6-7') ->
[E -> T - E]
T('2') + T('3*(4') - T('5)+6-7')

Формально правило применено верно.
ПС На каком основании вторую строку разбили по плюсу, а не минусу?

[usharik]

Думаю тут вопрос в точном определении того, что можно считать термой (подвыражением) типа T, а что нет. По меньшей мере она должна быть синтаксически корректно, а выражение с одной не закрытой скобкой явно не корректно.

[JackKatch]

Никлаус Вирт «Построение компиляторов». Проще не бывает.