В каком процессе возникает синтаксическая ошибка? (токенизация или разбор)

Я пытаюсь понять компиляцию и интерпретацию, шаг за шагом выясняя общее изображение. Поэтому я поднялся на вопрос, читая http://www.cs.man.ac.uk/~pjj/farrell/comp3.html эту статью.

Это говорит:

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

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

Он должен застрять там или дать неверную информацию парсеру. Я имею в виду, что токенизация не своего рода переводчик?

Так как же просто преодолеть лексические искаженные строки кода при токенизации.

Пример токена внутри ссылки выше под заголовком The Tokenizer .

Как я понимаю, форма токена выглядит так: если в коде что-то не так, токен тоже будет поврежден.

Не могли бы вы прояснить мое недоразумение?

compiler parsing interpreters FZE
источник

Ответы:

Токенизатор - это просто оптимизация парсера. Вполне возможно реализовать парсер без токенизатора.

Токенайзер (или лексер, или сканер) преобразует входные данные в список токенов. Некоторые части строки (комментарии, пробелы) обычно игнорируются. Каждый токен имеет тип (значение этой строки в языке) и значение (строка, которая составляет токен). Например, фрагмент исходного кода PHP

$a + $b

может быть представлен токенами

Variable('$a'),
Plus('+'),
Variable('$b')

Токенайзер не учитывает, возможен ли токен в этом контексте. Например, вход

$a $b + +

с удовольствием произвел бы поток токенов

Variable('$a'),
Variable('$b'),
Plus('+'),
Plus('+')

Когда анализатор затем использует эти токены, он заметит, что две переменные не могут следовать друг за другом, равно как и два инфиксных оператора. (Обратите внимание, что другие языки имеют разные синтаксисы, где такой поток токенов может быть допустимым, но не в PHP).

Синтаксический анализатор может все еще не работать на этапе токенизатора. Например, может быть недопустимый символ:

$a × ½ — 3

Токенайзер PHP не сможет сопоставить этот ввод с его правилами и выдаст ошибку перед началом основного анализа.

Более формально токенизаторы используются, когда каждый токен можно описать как обычный язык . Затем токены могут быть очень эффективно сопоставлены, возможно, реализованы как DFA. Напротив, основная грамматика обычно не зависит от контекста и требует более сложного, менее производительного алгоритма синтаксического анализа, такого как LALR.

Амон
источник

Таким образом, мы могли бы думать, что tokenizer является частью синтаксического анализатора, и синтаксическая ошибка может возникать либо на этапе токенизации, либо на этапе синтаксического анализа в соответствии с формой синтаксической ошибки. Благодарю за разъяснение.

FZE

@FZE: Вы могли бы так думать, но это вводит в заблуждение. Lexing - это не просто оптимизация парсера. Скорее, лексинг отображает физическое представление (некоторую последовательность символов) в логическое представление (токены, представленные этими символами). Это изолирует синтаксический анализатор от таких мелочей, как то, как представлен конец строки, или вы решаете представлять логическое - и как, andили как- &&то еще. Это (в основном) отдельно и отличается от анализа. Оптимизация (если есть) является почти случайным побочным эффектом.

Джерри Коффин

@JerryCoffin спасибо за дальнейшее объяснение, теперь оно имеет больше смысла.

FZE

@JerryCoffin, Amon правильно, то есть разница не принципиальна. Вы можете создать связную грамматику BNF, которая охватывает как части «лексер», так и «парсер». Мы обычно классифицируем правила на низкий уровень (например, число, оператор сложения) и высокий уровень (суммирование), но сама грамматика не делает такого различия.

Пол Дрэйпер

@PaulDraper Не уверен, что выделение обычного языка в качестве первого этапа - правильный выбор. Например, для описания строковых литералов в некоторых языках могут потребоваться сопоставленные пары (не регулярные), но все же имеет смысл обрабатывать их на первом этапе. Избегание / минимизация обратного отслеживания кажется лучшим руководством.

CodesInChaos

Вы бы обычно ожидать , что большинство ошибок синтаксиса исходить от синтаксического анализатора, а не лексер.

Лексер выдаст ошибку, если (и в основном только если) во входных данных будет что-то, что не может быть разбито на токены. Однако во многих языках практически любая последовательность символов может быть превращена в токены какого-либо рода, поэтому ошибки здесь довольно необычны.

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

Джерри Гроб
источник

Tokenizer просто разбивает поток символов на токены. От токенизатора POV это полностью действует:

1 * * 1

и переводит что-то вроде: ["1", MULTIPLY, MULTIPLY, "1"] Только парсер может отклонить такие выражения - он знает, что оператор умножения не может следовать за другим оператором умножения. Например, в JavaScript это производит:

Uncaught SyntaxError: Unexpected token *(…)

Есть ошибки, которые могут быть обнаружены токенизатором. Например незавершенные строковые литералы: "abcили недействительные номера: 0x0abcdefg. Хотя они все еще могут быть представлены как синтаксические ошибки:

Uncaught SyntaxError: Unexpected token ILLEGAL

Обратите внимание, что токен не был распознан и сообщается как ILLEGAL .

Banthar
источник