В информатике синтаксис компьютерного языка — это правила, определяющие комбинации символов, которые считаются правильно структурированными утверждениями или выражениями на этом языке. Это относится как к языкам программирования , где документ представляет собой исходный код , так и к языкам разметки , где документ представляет данные.
Синтаксис языка определяет его поверхностную форму. [1] Текстовые компьютерные языки основаны на последовательностях символов , тогда как языки визуального программирования основаны на пространственном расположении и связях между символами (которые могут быть текстовыми или графическими). Говорят, что документы, которые являются синтаксически недействительными, содержат синтаксическую ошибку . При разработке синтаксиса языка дизайнер может начать с записи примеров как допустимых, так и недопустимых строк , прежде чем пытаться на основе этих примеров выяснить общие правила. [2]
Таким образом, синтаксис относится к форме кода и противопоставляется семантике – значению . При обработке компьютерных языков семантическая обработка обычно идет после синтаксической обработки; однако в некоторых случаях для полного синтаксического анализа необходима семантическая обработка, и они выполняются вместе или одновременно . В компиляторе синтаксический анализ включает в себя интерфейсную часть , а семантический анализ — внутреннюю часть (и среднюю часть, если выделена эта фаза).
Синтаксис компьютерного языка обычно разделяют на три уровня:
Такое разграничение обеспечивает модульность, позволяя описывать и обрабатывать каждый уровень отдельно и часто независимо. Во-первых, лексер превращает линейную последовательность символов в линейную последовательность токенов; это известно как « лексический анализ » или «лексинг». Во-вторых, синтаксический анализатор превращает линейную последовательность токенов в иерархическое синтаксическое дерево; в узком смысле это называется « синтаксическим анализом ». В-третьих, контекстный анализ разрешает имена и проверяет типы. Такая модульность иногда возможна, но во многих реальных языках более ранний шаг зависит от последующего шага — например, хак лексера в C обусловлен тем, что токенизация зависит от контекста. Даже в этих случаях синтаксический анализ часто рассматривается как приближение к этой идеальной модели.
Сам этап синтаксического анализа можно разделить на две части: дерево синтаксического анализа , или «конкретное синтаксическое дерево», которое определяется грамматикой, но обычно слишком подробно для практического использования, и абстрактное синтаксическое дерево (AST), которое упрощает это в удобную форму. Шаги AST и контекстного анализа можно рассматривать как форму семантического анализа, поскольку они добавляют значение и интерпретацию синтаксису, или, альтернативно, как неформальную, ручную реализацию синтаксических правил, которые было бы сложно или неудобно описать или реализовать формально.
Уровни обычно соответствуют уровням иерархии Хомского . Слова написаны на обычном языке и определены в лексической грамматике , которая представляет собой грамматику типа 3, обычно выраженную в виде регулярных выражений . Фразы написаны на контекстно-свободном языке (CFL), обычно детерминированном контекстно-свободном языке (DCFL), указанном в грамматике структуры фразы , которая представляет собой грамматику типа 2, обычно задаваемую как правила производства в форме Бэкуса-Наура (BNF) . ). Фразовые грамматики часто задаются в виде гораздо более ограниченных грамматик, чем полные контекстно-свободные грамматики , чтобы облегчить их анализ; в то время как анализатор LR может анализировать любой DCFL за линейное время, простой анализатор LALR и даже более простой анализатор LL более эффективны, но могут анализировать только грамматики, правила производства которых ограничены. В принципе, контекстная структура может быть описана с помощью контекстно-зависимой грамматики и автоматически проанализирована с помощью таких средств, как грамматики атрибутов , хотя, как правило, этот шаг выполняется вручную, с помощью правил разрешения имен и проверки типов , и реализуется через таблицу символов. который хранит имена и типы для каждой области.
Написаны инструменты, автоматически генерирующие лексер из лексической спецификации, написанной в регулярных выражениях, и парсер из фразовой грамматики, написанной в BNF: это позволяет использовать декларативное программирование , а не необходимость иметь процедурное или функциональное программирование. Ярким примером является пара lex - yacc . Они автоматически создают конкретное синтаксическое дерево; затем автор синтаксического анализатора должен вручную написать код, описывающий, как он преобразуется в абстрактное синтаксическое дерево. Контекстный анализ также обычно выполняется вручную. Несмотря на существование этих автоматических инструментов, синтаксический анализ часто реализуется вручную по разным причинам — возможно, структура фразы не является контекстно-свободной, или альтернативная реализация повышает производительность или отчетность об ошибках, или позволяет упростить изменение грамматики. Парсеры часто пишутся на функциональных языках, таких как Haskell , или на языках сценариев, таких как Python или Perl , или на C или C++ .
Например, (add 1 1)это синтаксически допустимая программа на Лиспе (при условии, что функция «add» существует, иначе разрешение имени не удастся), добавляющее 1 и 1. Однако следующие значения недействительны:
(_ 1 1) лексическая ошибка: '_' недействителен(добавить 1 1 ошибка синтаксического анализа: отсутствует закрытие ')'
Лексер не может идентифицировать первую ошибку – все, что он знает, это то, что после создания токена LEFT_PAREN '(' оставшаяся часть программы недействительна, поскольку ни одно словесное правило не начинается с '_'. Вторая ошибка обнаруживается на этап синтаксического анализа: синтаксический анализатор определил правило производства «списка» благодаря токену '(' (как единственному совпадению) и, следовательно, может выдать сообщение об ошибке; в целом оно может быть неоднозначным .
Ошибки типа и ошибки необъявленных переменных иногда считаются синтаксическими ошибками, когда они обнаруживаются во время компиляции (что обычно имеет место при компиляции строго типизированных языков), хотя вместо этого принято классифицировать эти виды ошибок как семантические ошибки. [3] [4] [5]
Например, код Python
'а' + 1
содержит ошибку типа, поскольку к целочисленному литералу добавляется строковый литерал. Ошибки типа такого типа могут быть обнаружены во время компиляции: они могут быть обнаружены во время синтаксического анализа (анализа фраз), если компилятор использует отдельные правила, которые допускают «integerLiteral + IntegerLiteral», но не «stringLiteral + IntegerLiteral», хотя более вероятно, что компилятор будет использовать правило синтаксического анализа, которое разрешает все выражения вида «LiteralOrIdentifier + LiteralOrIdentifier», а затем ошибка будет обнаружена в ходе контекстного анализа (когда происходит проверка типа). В некоторых случаях эта проверка не выполняется компилятором, и эти ошибки обнаруживаются только во время выполнения.
В динамически типизированном языке, где тип может быть определен только во время выполнения, многие ошибки типов могут быть обнаружены только во время выполнения. Например, код Python
а + б
синтаксически допустим на уровне фразы, но правильность типов a и b может быть определена только во время выполнения, поскольку в Python переменные не имеют типов, а есть только значения. Хотя существуют разногласия относительно того, следует ли называть ошибку типа, обнаруженную компилятором, синтаксической ошибкой (а не статической семантической ошибкой), ошибки типа, которые могут быть обнаружены только во время выполнения программы, всегда рассматриваются как семантические, а не синтаксические ошибки.
Синтаксис текстовых языков программирования обычно определяется с использованием комбинации регулярных выражений (для лексической структуры) и формы Бэкуса-Наура (для грамматической структуры) для индуктивного определения синтаксических категорий (нетерминалов) и терминальных символов. Синтаксические категории определяются правилами, называемыми постановками , которые определяют значения, принадлежащие определенной синтаксической категории. [1] Терминальные символы — это конкретные символы или строки символов (например, такие ключевые слова , как define , if , let или void ), из которых создаются синтаксически допустимые программы.
Язык может иметь разные эквивалентные грамматики, такие как эквивалентные регулярные выражения (на лексическом уровне) или разные правила фраз, которые порождают один и тот же язык. Использование более широкой категории грамматик, такой как грамматики LR, может позволить создавать более короткие или простые грамматики по сравнению с более ограниченными категориями, такими как грамматика LL, для которой могут потребоваться более длинные грамматики с большим количеством правил. Различные, но эквивалентные грамматики фраз дают разные деревья синтаксического анализа, хотя базовый язык (набор действительных документов) один и тот же.
Ниже приведена простая грамматика, определенная с использованием обозначений регулярных выражений и расширенной формы Бэкуса-Наура . Он описывает синтаксис S-выражений , синтаксис данных языка программирования Lisp , который определяет продукции для синтаксических категорий выражение , атом , число , символ и список :
выражение = атом | атом списка = число | номер символа = [ + - ] ? [ '0' - '9' ] + символ = [ 'A' - 'Z' ][ 'A' - 'Z''0' - '9' ]. * список = '(' , выражение * , ')' Эта грамматика определяет следующее:
Здесь десятичные цифры, символы верхнего и нижнего регистра и круглые скобки являются терминальными символами.
Ниже приведены примеры правильно сформированных последовательностей токенов в этой грамматике: ' 12345', ' ()', ' (A B C232 (1))'
Грамматику, необходимую для определения языка программирования, можно классифицировать по ее положению в иерархии Хомского . Фразовая грамматика большинства языков программирования может быть определена с использованием грамматики типа 2, т. е. они являются контекстно-свободными грамматиками , [6] хотя общий синтаксис является контекстно-зависимым (из-за объявлений переменных и вложенных областей видимости), следовательно, тип- 1. Однако есть исключения: для некоторых языков фразовая грамматика относится к типу 0 (полная по Тьюрингу).
В некоторых языках, таких как Perl и Lisp, спецификация (или реализация) языка допускает конструкции, которые выполняются на этапе синтаксического анализа. Более того, в этих языках есть конструкции, которые позволяют программисту изменять поведение синтаксического анализатора. Эта комбинация эффективно стирает различие между синтаксическим анализом и выполнением и делает синтаксический анализ неразрешимой проблемой в этих языках, а это означает, что фаза синтаксического анализа может не завершиться. Например, в Perl можно выполнять код во время синтаксического анализа с использованием оператора BEGIN, а прототипы функций Perl могут изменять синтаксическую интерпретацию и, возможно, даже синтаксическую достоверность остального кода. [7] [8] В просторечии это называется «только Perl может анализировать Perl» (поскольку код должен выполняться во время синтаксического анализа и может изменять грамматику) или, более строго, «даже Perl не может анализировать Perl» (потому что это неразрешимо). ). Точно так же макросы Lisp, представленные синтаксисом, defmacroтакже выполняются во время синтаксического анализа, а это означает, что в компиляторе Lisp должна присутствовать вся система времени выполнения Lisp. Напротив, макросы C представляют собой просто замену строк и не требуют выполнения кода. [9] [10]
Синтаксис языка описывает форму допустимой программы, но не предоставляет никакой информации о значении программы или результатах ее выполнения. Значение, придаваемое комбинации символов, обрабатывается семантикой (либо формальной , либо жестко запрограммированной в эталонной реализации ). Не все синтаксически правильные программы являются семантически правильными. Тем не менее, согласно правилам языка, многие синтаксически правильные программы имеют неверный формат; и может (в зависимости от спецификации языка и правильности реализации) привести к ошибке при трансляции или выполнении. В некоторых случаях такие программы могут демонстрировать неопределенное поведение . Даже если программа четко определена в языке, она все равно может иметь значение, которое не было задумано человеком, который ее написал.
На примере естественного языка может оказаться невозможным придать значение грамматически правильному предложению или предложение может оказаться ложным:
Следующий фрагмент языка C синтаксически корректен, но выполняет операцию, которая не определена семантически (поскольку pэто нулевой указатель , операции и не имеют смысла):p->realp->im
комплекс * р = NULL ; комплекс abs_p = sqrt ( p -> real * p -> real + p -> im * p -> im ); В качестве более простого примера,
интервал х ; printf ( "%d" , x ); синтаксически допустим, но не определен семантически, поскольку использует неинициализированную переменную . Хотя компиляторы некоторых языков программирования (например, Java и C#) обнаруживают ошибки неинициализированных переменных такого типа, их следует рассматривать как семантические , а не синтаксические ошибки. [5] [11]
Чтобы быстро сравнить синтаксис различных языков программирования, взгляните на список «Hello, World!» примеры программ :