Попытка понять синтаксический анализ и сканирование (разница для языков reg. И cf)

Во-первых, я не изучаю информатику, меня просто интересует предмет.

Парсер в основном делает это правильно:

  1. чтение ввода
  2. создавать токены
  3. собственно разобрать токены и создать AST

Поэтому я подумал, что для того, чтобы решить, принадлежит ли слово к обычному языку, вы используете автомат, а для языков CF вам понадобится синтаксический анализатор из-за рекурсивных структур, которые могут существовать. Следовательно, существуют генераторы сканеров для обычных языков и генераторы парсеров для языков CF.

Но теперь я прочитал, что вы можете создать рекурсивный приличный парсер для регулярных выражений:

http://matt.might.net/articles/parsing-regex-with-recursive-descent/

Так как же все это происходит вместе?

Зачем мне разбирать обычные языки? Я думал, что конечного автомата достаточно?

Если, например, Я хочу распознавать блочные комментарии в java-программе (т.е. /* .. */), мне нужно только написать FSM, так что в основном оператор switch-case-statement. Парсер мне для этого не нужен ...

Спасибо за помощь и разъяснения!


parsing regex regular-language context-free-language
person user3629892    schedule 31.03.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Есть разница между тем, что может соответствовать регулярному выражению, и тем, что вам нужно для синтаксического анализа регулярного выражения. Регулярные выражения могут, например, содержать вложенные группы, поэтому вы не можете анализировать их с помощью регулярного выражения. Например, вам нужно «подсчитать» вложенные пары скобок, что выходит за рамки возможностей обычного языка.

См. Также: Существует ли регулярный язык для представления регулярных выражений .

person BlackJack    schedule 31.03.2015
comment
ааа ... так что регулярные выражения сами по себе не регулярные языки, а только то, что они соответствуют? Итак, чтобы проверить, находится ли что-то в пределах обычного языка, вы используете автомат, но само регулярное выражение должно быть проанализировано? Но все же: мне нужен только парсер для языков CF? Для RL достаточно автомата? - person user3629892; 31.03.2015
comment
Что здесь за «парсер»? Например, функция C scanf() используется для синтаксического анализа строковых представлений на различные базовые типы данных, такие как числа или строки. В JavaScript есть функция parseInt() для преобразования строки в число. Обоим не требуется ничего, кроме реализации, подобной FSM, для анализа ввода. И да, для разбора RL достаточно автомата. - person BlackJack; 31.03.2015
comment
хм, ладно ... Я думал, что синтаксический анализатор означает, что существует синтаксическое дерево ... а в случае parseInt, например, он назывался сканером ... - person user3629892; 08.04.2015