Руководство по проектированию для синтаксического анализатора и лексического анализатора?

Я пишу лексический анализатор (с re2c) и синтаксический анализатор (с Лимоном) для немного замысловатого формата данных: подобный CSV, но с определенными строковыми типами в определенных местах (алфавитно-цифровые символы только, алфавитно-цифровые символы и знаки "минус", любой символ кроме кавычек и запятой, но со сбалансированными фигурными скобками, и т.д.), строки в фигурных скобках и строки, которые похожи на вызовы функции с открытием и закрывающими фигурными скобками, которые могут содержать параметры.

Мой первый выстрел в него был лексическим анализатором со многими состояниями, каждое состояние, угождающее определенному формату строки. Но после того, как много бесполезных "неожиданных входов" обмениваются сообщениями из лексического анализатора (который стал очень большим), я понял, что, возможно, он пытался сделать работу синтаксического анализатора. Я фрагментировал свое первое, пытаются, пошел с лексическим анализатором только с одним состоянием, многими символьными маркерами и синтаксическим анализатором, который комбинирует маркеры в различные строковые типы. Это работает лучше, я получаю более полезные синтаксические ошибки из синтаксического анализатора, когда что-то выключено, но он все еще не совсем чувствует себя хорошо. Я думаю о добавлении одного или двух состояний к лексическому анализатору, но инициирование состояния из синтаксического анализатора, который имеет намного лучший "обзор", на котором строковый тип требуется в приведенном примере. В целом я чувствую себя немного глупым :(

Я не имею никакого формального фона CS и пугаюсь немного далеко от тяжелой математикой теории. Но возможно существует учебное руководство или книга где-нибудь, которая объясняет, что лексический анализатор должен (и не должен) делать и какую часть работы синтаксический анализатор должен сделать. Как создать хорошие маркерные шаблоны, когда использовать состояния лексического анализатора, когда и как использовать рекурсивные правила (с LALR-парсером), как избежать неоднозначных правил. Прагматическая поваренная книга, которая преподает основы. "Закон и КРАТКАЯ ИНФОРМАЦИЯ/ПРАКТИЧЕСКОЕ РУКОВОДСТВО YACC" были хороши, но недостаточно. Так как я просто хочу проанализировать формат данных, книги по зданию компилятора (как красная книга дракона) выглядят немного увеличенного размера мне.

Или возможно кто-то может дать мне некоторые простые правила здесь.

6
задан chiborg 7 July 2010 в 09:18
поделиться

1 ответ

Что вам действительно следует сделать, так это написать грамматику для вашего языка. Как только вы ее получите, границы будут простыми:

  • Лексер отвечает за прием входных данных и сообщает вам, какой терминал у вас есть.
  • Синтаксический анализатор отвечает за сопоставление серии терминалов и нетерминалов с правилом производства, многократно, пока вы не получите либо дерево разбора, либо ошибку разбора.

Лексер не отвечает за проверку ввода, кроме как в части отбраковки невозможных символов и других очень базовых битов. Все это делает синтаксический анализатор.

Посмотрите на http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html . Это страница вводного курса CS по синтаксическому анализу.

7
ответ дан 9 December 2019 в 20:39
поделиться
Другие вопросы по тегам:

Похожие вопросы: