Является ли лексическая грамматика Rust регулярной, контекстно-свободной или контекстно-зависимой?
Лексическая грамматика большинства языков программирования довольно не выразительна, чтобы быстро ее выучить. Я не уверен, к какой категории относится лексическая грамматика Rust. Большинство из них кажется регулярным, возможно, за исключением необработанных строковых литералов:
let s = r##"Hi lovely "\" and "#", welcome to Rust"##;
println!("{}", s);
Какие отпечатки:
Hi lovely "\" and "#", welcome to Rust
Как мы можем добавить произвольно много # кажется, что это не может быть регулярным, верно? Но является ли грамматика хотя бы контекстно-свободной? Или в лексической грамматике Руста есть что-то неконтролируемое?
Связанный: Является ли синтаксическая грамматика Rust контекстно-зависимой или контекстно-зависимой?
1 ответ
Синтаксис необработанного строкового литерала не является контекстно-свободным.
Если вы думаете об этом как о струне, окруженной r#k"…"#k (используя верхний индекс k как оператор подсчета), то вы можете ожидать, что он будет свободен от контекста:
raw_string_literal
: 'r' delimited_quoted_string
delimited_quoted_string
: quoted_string
| '#' delimited_quoted_string '#'
Но это не совсем правильный синтаксис, потому что quoted_string не может содержать "#k хотя может содержать "#j для любого j<k
Исключение завершающей последовательности без исключения любой другой подобной последовательности другой длины не может быть выполнено с помощью контекстно-свободной грамматики, поскольку она включает три (или более) использования k-повторение в одном производстве, а стек автоматов может обрабатывать только два. (Доказательство того, что грамматика не является контекстно-свободной, на удивление сложное, поэтому я не собираюсь делать это здесь из-за отсутствия MathJax. Лучшее доказательство, которое я мог бы придумать, использует лемму Огдена и необычно цитируемые (но очень полезные) свойство, что контекстно-свободные грамматики закрыты при применении конечного преобразователя.)
Необработанные строковые литералы C++ также являются контекстно-зависимыми [или были бы, если бы длина разделителя не была ограничена, см. Примечание 1], и довольно хорошо все чувствительные к пробелам языки (такие как Python и Haskell) чувствительны к контексту. Ни одна из этих задач лексического анализа не является особенно сложной, поэтому чувствительность к контексту не является большой проблемой, хотя большинство стандартных генераторов сканеров не предоставляют столько помощи, сколько хотелось бы. Но это так.
Лексическая грамматика Rust предлагает несколько других усложнений для генератора сканера. Одной из проблем является двойное значение ', которое используется как для создания символьных литералов, так и для маркировки переменных времени жизни и меток цикла. По-видимому, можно определить, какое из них применимо, с учетом ранее распознанного токена. Это можно решить с помощью лексического сканера, который способен генерировать два последовательных токена из одного шаблона, или это можно сделать с помощью анализатора без сканера; последнее решение будет не зависящим от контекста, но не регулярным. (Использование C++ в качестве части числовых литералов не вызывает той же проблемы; токены C++ могут быть распознаны с помощью регулярных выражений, потому что " нельзя использовать в качестве первого символа числового литерала.)
Еще одна слегка зависящая от контекста лексическая проблема заключается в том, что оператор .., имеет приоритет над значениями с плавающей запятой, так что 2..3 должен быть лексически проанализирован как три токена: 2 .. 3, а не как два числа с плавающей запятой 2. .3, как это будет анализироваться в большинстве языков, которые используют правило максимального жаворонка. Опять же, это может или не может рассматриваться как отклонение от токенизации регулярного выражения, так как это зависит от конечного контекста. Но поскольку предвидение не более одного символа, оно, безусловно, может быть реализовано с помощью DFA.
постскриптум
Поразмыслив, я не уверен, что имеет смысл спрашивать о "лексической грамматике". Или, по крайней мере, это неоднозначно: "лексическая грамматика" может относиться к объединенной грамматике для всех языков "токены", или она может относиться к акту разделения предложения на токены. Последний действительно является преобразователем, а не анализатором, и предлагает вопрос о том, может ли язык быть токенизирован с помощью преобразователя с конечным состоянием. (Ответ, опять же, нет, потому что необработанные строки не могут быть распознаны FSA или даже PDA.)
Распознавание отдельных токенов и токенизация входного потока не обязательно эквивалентны. Можно представить язык, на котором все отдельные токены распознаются регулярными выражениями, но входной поток не может быть обработан с помощью преобразователя конечных состояний. Это произойдет, если есть два регулярных выражения T а также U такой, что какое-то соответствие строки T это самый длинный токен, который является строгим префиксом бесконечного набора строк в U, В качестве простого (и бессмысленного) примера возьмем язык с токенами:
a
a*b
Оба эти токена явно регулярны, но входной поток нельзя токенизировать с помощью датчика конечного состояния, поскольку он должен исследовать любую последовательность a s (любой длины), прежде чем решить, следует ли вернуться к первому a или принять токен, состоящий из всех a с и следующее b (если представить).
Немногие языки показывают эту патологию (и, насколько мне известно, Rust не является одним из них), но она технически присутствует в некоторых языках, в которых ключевые слова являются многословными фразами.
Заметки
- Фактически, необработанные строковые литералы C++ в техническом смысле являются регулярными (и, следовательно, свободными от контекста), поскольку их разделители ограничены строками максимальной длины 16, взятыми из алфавита из 88 символов. Это означает, что (теоретически) возможно создать регулярное выражение, состоящее из 13 082 362 351 752 551 144 309 757 252 761 шаблонов, каждый из которых соответствует различному возможному необработанному разделителю строк.