M
А как же проблема поста?
Size: a a a
2021 March 22
M
Поиск неоднозначности это вроде эврестический алгоритм
EM
Такой вопрос, а есть какие то грамматики гарантирующие отсутствия неоднозначности? На которых можно писать языки программирования, к примеру мейнтсримовые
Есть система типов для грамматик, гарантирующая однозначность :)
https://www.cl.cam.ac.uk/~jdy22/papers/a-typed-algebraic-approach-to-parsing.pdf
https://www.cl.cam.ac.uk/~jdy22/papers/a-typed-algebraic-approach-to-parsing.pdf
M
M
Можно ещё старым добрым брутфорсом
K
Такой вопрос, а есть какие то грамматики гарантирующие отсутствия неоднозначности? На которых можно писать языки программирования, к примеру мейнтсримовые
Есть, LR(1)
M
Вопрос исследовательский скорей
K
Вопрос исследовательский скорей
LR(1) является наибольших классом грамматик без неоднозначностей
f
LR(1) является наибольших классом грамматик без неоднозначностей
LR(k)?
f
Утверждается, что PEG без неоднозначностей и больше, но есть один нюанс 😉
M
Отсутствует один из видов рекурсии
M
Вроде бы
K
Отсутствует один из видов рекурсии
Ниет, там просто
/ - это left-biased-choice, он тупо прячет все конфликтыK
А, ну и да, нет левой рекурсии
f
Да, PEG "решает" проблему леса, игнорируя деревья, которым не повезло.
f
С тем же успехом в LR можно игнорировать reduce-reduce конфликты. Некоторые так и делают в промышленных парсерах.
YS
Утверждается, что PEG без неоднозначностей и больше, но есть один нюанс 😉
И он в том, что это — не грамматики. ;)
K
Yaroslav Schekin
И он в том, что это — не грамматики. ;)
А, ну да)
VK
Yaroslav Schekin
И он в том, что это — не грамматики. ;)
в смысле? PEG это *другой* формализм, конечно, не такой традиционный, но значительно более удобный в разборе.
s
в смысле? PEG это *другой* формализм, конечно, не такой традиционный, но значительно более удобный в разборе.
А есть ли какая-нибудь логическая семантика у этого вашего пега?