Недавно я наткнулся на учебное пособие по контекстно-свободным грамматикам с несколькими примерами общих шаблонов, которые вы можете найти в этих грамматиках, и я подумал про себя — почему бы не реализовать некоторые из этих примеров в качестве упражнения?
Сначала мне нужно было выбрать язык Java и инструменты для реализации примеров с помощью JFlex и Джек . Эта пара достаточно похожа на Flex и Bison, и, надеюсь, грамматики не будут затенены реализацией.
Я познакомился с Flex и Yacc и сделал три заметки о работе с ними:
- Познакомьтесь с JFlex — введение в JFlex с небольшим примером автономного лексера,
- Используйте JFlex для подсчета слов — еще один пример автономного лексера, на этот раз немного более сложный,
- Используйте JFlex и Jacc вместе — как заставить JFlex и Jacc сотрудничать, также с элементарным примером.
Если вы заинтересованы в CFG и синтаксическом анализе, учебное пособие, о котором я упоминал, – неплохое место, чтобы получить некоторый практический опыт их реализации. Вы можете найти его здесь и я также загрузил его в Github (надеясь, что не нарушил никаких законов об авторском праве).
Грамматика, которую я использовал, чтобы продемонстрировать, как Flex и Jacc работают вместе, на самом деле является грамматикой из раздела 2.1 руководства (“Грамматика для языка, который допускает список X”) так что на самом деле я уже начал выполнять упражнения. Ура.
Использование Graphviz вы можете получить визуальное представление ваших грамматик. Сначала экспортируйте грамматику в виде точечного файла:
jacc -d Parser.jacc
Это создает Parser.dot. Затем
dot -Tjpg Parser.dot -o Parser.jpg
и в итоге вы получаете Parser.jpg . Это очень просто:
Это конечный автомат, представленный в виде ориентированного графа. Создание визуальных представлений грамматики – это всего лишь один из инструментов, предоставляемых Jacc для отладки ваших грамматик. Вы можете экспортировать грамматику в текстовый файл:
jacc -v Parser.jacc
Это создает Parser.output:
// Output created by jacc on Wed Mar 13 09:15:29 CET 2019
state 0 (entry on sentence)
$accept : \_sentence $end
X shift 2
. error
sentence goto 1
state 1 (entry on sentence)
$accept : sentence\_$end
sentence : sentence\_X (2)
$end accept
X shift 3
. error
state 2 (entry on X)
sentence : X\_ (1)
$end reduce 1
X reduce 1
. error
state 3 (entry on X)
sentence : sentence X\_ (2)
$end reduce 2
X reduce 2
. error
4 terminals, 1 nonterminals;
2 grammar rules, 4 states;
0 shift/reduce and 0 reduce/reduce conflicts reported.
или в html-файл:
jacc -h Parser.jacc
Это создает ParserMachine.html:
Сгенерированная машина для синтаксического анализатора
// Output created by jacc on Wed Mar 13 09:20:03 CET 2019
state 0 (entry on sentence) $accept : _sentence $end X shift 2 . error sentence goto 1
state 1 (entry on sentence) $accept : sentence_$end sentence : sentence_X (2) $end accept X shift 3 . error
state 2 (entry on X) sentence : X_ (1) $end reduce 1 X reduce 1 . error
state 3 (entry on X) sentence : sentence X_ (2) $end reduce 2 X reduce 2 . error 4 terminals, 1 nonterminals; 2 grammar rules, 4 states; 0 shift/reduce and 0 reduce/reduce conflicts reported.
Вы действительно можете просмотреть состояния машины, перейдя по ссылкам.
Jacc также поддерживает отслеживание вашей грамматики на примерах входных данных и встраивание пользовательских ошибок в грамматики — вот и все. ttfn!
Оригинал: “https://dev.to/vicentemaldonado/a-context-free-grammar-tutorial-38b5”