Предложения по написанию парсера, который читает CFG и удаляет левую рекурсию

Question

Мне нужен совет по написанию парсера (использующего C и Lex), который принимает CFG и удаляет левую рекурсию. Поскольку синтаксический анализатор должен принимать любую строку и грамматику, я понятия не имею, как начать. Хотя я знаком с алгоритмом удаления левого рекурсоина (как уже упоминалось здесь , я не знаю, как начать, и какие структуры данных будут задействованы. Каков наилучший способ хранения грамматики, и и как я могу эффективно применить алгоритм. Пожалуйста, предложите. (Поскольку это домашняя работа, пожалуйста, , не предоставьте мне код, вместо этого подойдет любая другая помощь / псевдокод):)

Answer 1

1. Вам нужно определить грамматику P, которая описывает грамматику. Это должно быть довольно легко.
2. Вам нужно создать парсер для P. Это не должно быть сложным, потому что P не будет сложным. Доверьтесь мне. Вы можете использовать этот метод для ручного кодирования синтаксического анализатора с рекурсивным спуском: https://stackoverflow.com/a/2336769/120163
3. Когда P анализирует, он создает структуру данных, представляющую грамматику. Такая структура данных должна записывать для каждого правила его левую сторону, длину и токены, составляющие тело правила.
4. На данный момент вы собрали правила в структуре данных, и теперь вам нужно применить левый алгоритм рекурсии, изменив правила.
5. Наконец, вам нужно распечатать правила; они должны появиться в том синтаксисе, который вы выбрали для P.