Обязанности Lexer и Parser

В настоящее время я использую lexer для простого языка программирования. До сих пор я могу точно идентифицировать идентификаторы, символы назначения и целочисленные литералы; в общем, пробелы несущественны.

Для входа foo = 42 распознаются три токена:

  1. foo (идентификатор)
  2. = (символ)
  3. 42 (целочисленный литерал)

Все идет нормально. Однако рассмотрим вход foo = 42bar, который является недопустимым из-за (значительного) недостающего места между 42 и bar. Мой лексер неправильно распознает следующие токены:

  1. foo (идентификатор)
  2. = (символ)
  3. 42 (целочисленный литерал)
  4. bar (идентификатор)

Как только лексер видит цифру 4, он продолжает читать, пока не встретит не цифру. Поэтому он потребляет 2 и сохраняет 42 как цельный литерал. Поскольку пробелы несущественны, лексер отбрасывает любые пробелы (если они есть) и начинает читать следующий токен: он находит bar идентификаторов.

Теперь, вот мой вопрос: не стоит ли лексеру признать, что идентификатор не разрешен в этой позиции? Или эта проверка относится к обязанностям синтаксического анализатора?

4 ответа

Я не думаю, что есть какой-либо консенсус относительно вопроса о том, следует ли признать 42foo как недопустимое число или как два токена. Вопрос о стиле и обоих обычаях распространен в хорошо известных языках.

Например:

$ python -c 'print 42and False'
False

$ lua -e 'print(42and false)'
lua: (command line):1: malformed number near '42a'

$ perl -le 'print 42and 0'
42

# Not an idiosyncracy of tcc; it defined by the standard
$ tcc -D"and=&&" -run - <<<"main(){return 42and 0;}"
stdin:1: error: invalid number

# gcc has better error messages
$ gcc -D"and=&&" -x c - <<<"main(){return 42and 0;}" && ./a.out
<stdin>: In function ‘main:
<stdin>:1:15: error: invalid suffix "and" on integer constant
<stdin>:1:21: error: expected ‘; before numeric constant

$ ruby -le 'print 42and 1'
42

# And now for something completely different (explained below)
$ awk 'BEGIN{print 42foo + 3}'
423
</stdin></stdin></stdin>

Таким образом, обе возможности широко используются.

Если вы собираетесь отклонить его, потому что вы считаете, что число и слово должны быть разделены пробелом, вы должны отклонить его в лексере. Парсер не может (или не должен) знать, разделяет ли пробел два токена. Независимо от действительности 42and и фрагменты 42 + 1, 42+1 и 42+ 1) должны быть проанализированы одинаково. (За исключением, возможно, в Крепости. Но это была аномалия.) Если вы не возражаете объединять числа и слова вместе, пусть пусть парсер отвергает его, если (и только если) это синтаксическая ошибка.

Как побочная заметка, в C и C++, 42and и первоначально лексируется как "номер препроцессора". После предварительной обработки его необходимо перевести, и именно в этот момент появляется сообщение об ошибке. Причиной этого странного поведения является то, что вполне законно вставлять вместе два фрагмента для получения действительного числа:

$ gcc -D"c_(x,y)=x##y" -D"c(x,y)=c_(x,y)" -x c - <<<"int main(){return c(12E,1F);}"
$ ./a.out; echo $?
120

Как 12E и 1F будут недопустимыми целыми числами, но вставляются вместе с оператором ##, они образуют совершенно законный поплавок. Оператор ## работает только с одиночными токенами, поэтому 12E и 1F оба должны лексироваться как одиночные токены. c(12E+,1F) не будет работать, но c(12E0,1F) также прекрасен.

Вот почему вы всегда должны помещать пробелы вокруг оператора + в C: классический трюк. Вопрос: "Что такое значение 0x1E+2?"

Наконец, объяснение для строки awk:

$ awk 'BEGIN{print 42foo + 3}'
423

Это lexed awk как BEGIN{print 42 foo + 3} который затем разбирается, как если бы он был написан BEGIN{print (42)(foo + 3);}. В awk конкатенация строк записывается без оператора, но она связывается менее жестко, чем любой арифметический оператор. Следовательно, обычный совет состоит в том, чтобы использовать явные скобки в выражениях, которые связаны с конкатенацией, если они не являются действительно простыми. (Кроме того, предполагается, что неопределенные переменные имеют значение 0 если они используются арифметически и "" если они используются как строки.)


Я не согласен с другими ответами здесь. Это должно быть сделано лексером. Если символ, следующий за цифрами, не является пробелом или специальным символом, вы находитесь в середине незаконного токена, в частности, идентификатора, который не начинается с буквы.

Или просто верните 45 и "бар" отдельно и пусть парсер обрабатывает его как синтаксическую ошибку.


Да, такие контекстные проверки относятся к парсеру.

Кроме того, вы говорите, что foo = 42bar недействителен. Однако с точки зрения лексера это не так. 4 токена, распознанные вашим лексером (вероятно) правильные (вы не публикуете свои определения токенов).

foo = 42bar может быть или не быть действительным выражением на вашем языке.


Изменение: я просто понял, что это действительно недействительный токен для вашего языка. Так что да, это не поможет лексеру в этот момент, потому что у вас нет правила, соответствующего ему. В противном случае, что бы это было, InvalidTokenToken?

Но пусть говорят, что это действительный знак. Скажем, вы пишете правило lexer, в котором говорится, что id = в порядке... что вы делаете с id = <number> + <number> - </number> </number> и все различные комбинации, к которым это ведет? Как лексер собирается дать вам АСТ для любого из них? Вот где входит парсер.

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

licensed under cc by-sa 3.0 with attribution.