От BNF-подобного грамматика до Java или переполнения стека
Я искал в Интернете, чтобы найти ответ, но я не мог. Есть ли кто-нибудь, кто поможет мне?
expr ->term moreterms
moreterms -> +term {print(‘+’)} moreterms
|‐term {print(‘‐’)} moreterms
|ε
term ->factor morefactors
morefactors ->*factor {print(‘*’)} morefactors
|/factor {print(‘/’)} morefactors
|ε
factor ->(expr)
|id {print(id)}
|num {print(num)}
Я буду использовать этот код для очень простого компилятора калькулятора и интерпретатора.
Как я могу преобразовать этот грамматик в C ++ или Java?
Решение
Есть много инструментов, которые берут грамматику и генерируют парсеры, начиная от Yacc для повышения духа.
Искусство написания парсеров широко изучено. Это не тривиально. Один из подходов состоит в том, чтобы определить, можете ли вы превратить ваш BNF в грамматику LR (1) и написать для нее LR-парсер.
Простой способ разбора — разделить ваш анализ на токенизацию (где вы объединяете вещи в идентификаторы) и генерацию синтаксического дерева.
Википедия имеет краткое описание синтаксического анализа LR. Кнута Канонический парсер LR (1) Также стоит посмотреть.
Обучение написанию парсера LR (1) (с любыми ограничениями, не говоря уже о парсере LR (k)) — это вопрос короткого курса в колледже или главы книги, а не сообщения о переполнении стека.
Но общая идея заключается в том, что вы читаете слева направо. Вы смотрите вперед k токенов (обычно 1), чтобы определить, какое правило применить к следующему токену, с которым вы столкнетесь. Вы строите дерево разбора снизу вверх.
Есть много технических деталей, приемов, причуд и проблем. Не каждую грамматику BNF можно превратить в грамматику LR (1), не говоря уже об ограниченных, которые могут обрабатывать многие генераторы разбора.
Как упомянуто @UnholySheep, Дракон Книга это книга, из которой большинство людей изучают эти методы.
Другие решения
Вы смотрели на Yacc? Это может быть именно то, что вы ищете.