От BNF-подобного грамматика до Java или C++

Question

Я искал в Интернете, чтобы найти ответ, но я не мог. Есть ли кто-нибудь, кто поможет мне?

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?

Answer 1

Существует множество инструментов, которые берут грамматики и генерируют парсеры, начиная от Yacc и повышая дух.

Искусство написания парсеров широко изучено. Это не тривиально. Один из подходов состоит в том, чтобы определить, можете ли вы сделать свой BNF в грамматике LR (1) и написать для него парсер LR.

Простым способом анализа является разделение вашего синтаксического анализа на токенизацию (где вы связываете вещи в идентификаторы) и генерация синтаксического дерева.

Wikipedia имеет беглое описание анализа LR. Также стоит посмотреть на Knuth's Canonical LR(1) parser.

Преподавание, как написать парсер LR (1), с любыми ограничениями, не говоря уже о парсере LR (k), - это короткий курс колледжа или глава книги, а не столбец переполнения стека.

Но общая идея заключается в том, что вы читаете слева направо. Вы смотрите вперед tokens (обычно 1), чтобы определить, какое правило применяется к следующему токену, с которым вы сталкиваетесь. Вы создаете дерево разбора снизу вверх.

Существует множество технических деталей, приемов, причуд и проблем. Не каждая грамматика BNF может быть превращена в грамматику LR (1), не говоря уже о ограниченных, которые могут обрабатывать многие генераторы синтаксического анализа.

As mentioend by @UnholySheep, TheDragonBook - это книга, из которой большинство людей изучают эти техники.

Answer 2

У вас есть Yacc? Это может делать именно то, что вы ищете.