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