Синтаксис (языки программирования)

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

Синтаксис языка определяет его поверхностную форму. ^[1] Текстовые компьютерные языки основаны на последовательностях символов , тогда как языки визуального программирования основаны на пространственном расположении и связях между символами (которые могут быть текстовыми или графическими). Говорят, что документы, которые являются синтаксически недействительными, содержат синтаксическую ошибку . При разработке синтаксиса языка разработчик может начать с записи примеров как допустимых, так и недопустимых строк , прежде чем пытаться на основе этих примеров выяснить общие правила. ^[2]

Таким образом, синтаксис относится к форме кода и противопоставляется семантике – значению . При обработке компьютерных языков семантическая обработка обычно происходит после синтаксической обработки; однако в некоторых случаях для полного синтаксического анализа необходима семантическая обработка, и они выполняются вместе или одновременно . В компиляторе синтаксический анализ включает в себя интерфейсную часть , а семантический анализ — внутреннюю часть (и среднюю часть, если выделяется эта фаза).

Уровни синтаксиса

Синтаксис компьютерного языка обычно разделяют на три уровня:

Слова – лексический уровень, определяющий, как символы образуют токены ;
Фразы – уровень грамматики, узко говоря, определяющий, как лексемы образуют фразы;
Контекст – определение того, к каким объектам или переменным относятся имена, допустимы ли типы и т. д.

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

Во-первых, лексер превращает линейную последовательность символов в линейную последовательность токенов; это известно как « лексический анализ » или «лексинг». ^[3]

Во-вторых, синтаксический анализатор превращает линейную последовательность токенов в иерархическое синтаксическое дерево; в узком смысле это называется « синтаксическим анализом ». Это гарантирует, что строка токенов соответствует формальным грамматикам языка программирования. Сам этап синтаксического анализа можно разделить на две части: дерево синтаксического анализа , или «конкретное синтаксическое дерево», которое определяется грамматикой, но обычно слишком подробно для практического использования, и абстрактное синтаксическое дерево (AST), которое упрощает это в удобную форму. Шаги AST и контекстного анализа можно рассматривать как форму семантического анализа, поскольку они добавляют значение и интерпретацию синтаксису, или, альтернативно, как неформальную, ручную реализацию синтаксических правил, которые было бы сложно или неудобно описать или реализовать формально.

В-третьих, контекстный анализ разрешает имена и проверяет типы. Такая модульность иногда возможна, но во многих реальных языках более ранний шаг зависит от последующего шага — например, хак лексера в C обусловлен тем, что токенизация зависит от контекста. Даже в этих случаях синтаксический анализ часто рассматривается как приближение к этой идеальной модели.

Уровни обычно соответствуют уровням иерархии Хомского . Слова написаны на обычном языке , указанном в лексической грамматике , которая представляет собой грамматику типа 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)    lexical error: '_' is not valid
(add 1 1   parsing error: missing closing ')'

Лексер не может идентифицировать первую ошибку – все, что он знает, это то, что после создания токена LEFT_PAREN '(' оставшаяся часть программы недействительна, поскольку ни одно словесное правило не начинается с '_'. Вторая ошибка обнаруживается на этап синтаксического анализа: синтаксический анализатор определил правило производства «списка» благодаря токену '(' (как единственному совпадению) и, следовательно, может выдать сообщение об ошибке; в целом оно может быть неоднозначным .

Ошибки типа и ошибки необъявленных переменных иногда считаются синтаксическими ошибками, если они обнаруживаются во время компиляции (что обычно имеет место при компиляции строго типизированных языков), хотя вместо этого принято классифицировать эти виды ошибок как семантические ошибки. ^[4]^[5]^[6]

Например, код Python

'a' + 1

содержит ошибку типа, поскольку к целочисленному литералу добавляется строковый литерал. Ошибки типов такого типа могут быть обнаружены во время компиляции: они могут быть обнаружены во время синтаксического анализа (анализа фраз), если компилятор использует отдельные правила, которые допускают «integerLiteral + IntegerLiteral», но не «stringLiteral + IntegerLiteral», хотя более вероятно, что компилятор будет использовать правило синтаксического анализа, которое разрешает все выражения вида «LiteralOrIdentifier + LiteralOrIdentifier», а затем ошибка будет обнаружена в ходе контекстного анализа (когда происходит проверка типа). В некоторых случаях эта проверка не выполняется компилятором, и эти ошибки обнаруживаются только во время выполнения.

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

a + b

синтаксически допустим на уровне фразы, но правильность типов a и b может быть определена только во время выполнения, поскольку в Python переменные не имеют типов, а есть только значения. Хотя существуют разногласия по поводу того, следует ли называть ошибку типа, обнаруженную компилятором, синтаксической ошибкой (а не статической семантической ошибкой), ошибки типа, которые могут быть обнаружены только во время выполнения программы, всегда рассматриваются как семантические, а не синтаксические ошибки.

Определение синтаксиса

Синтаксис текстовых языков программирования обычно определяется с использованием комбинации регулярных выражений (для лексической структуры) и формы Бэкуса-Наура ( метаязыка для грамматической структуры) для индуктивного определения синтаксических категорий ( нетерминальных ) и терминальных символов. ^[7] Синтаксические категории определяются правилами, называемыми постановками , которые определяют значения, принадлежащие определенной синтаксической категории. ^[1] Терминальные символы — это конкретные символы или строки символов (например, такие ключевые слова, как define , if , let или void ), из которых создаются синтаксически допустимые программы.

Синтаксис можно разделить на контекстно-свободный синтаксис и контекстно-зависимый синтаксис. ^[7] Контекстно-свободный синтаксис — это правила, определяемые метаязыком языка программирования. Они не будут ограничены контекстом, окружающим или ссылающимся на эту часть синтаксиса, в отличие от контекстно-зависимого синтаксиса.

Язык может иметь разные эквивалентные грамматики, такие как эквивалентные регулярные выражения (на лексическом уровне) или разные правила фраз, которые порождают один и тот же язык. Использование более широкой категории грамматик, такой как грамматики LR, может позволить создавать более короткие или простые грамматики по сравнению с более ограниченными категориями, такими как грамматика LL, для которой могут потребоваться более длинные грамматики с большим количеством правил. Различные, но эквивалентные грамматики фраз дают разные деревья синтаксического анализа, хотя базовый язык (набор действительных документов) один и тот же.

Пример: S-выражения Lisp

Ниже приведена простая грамматика, определенная с использованием обозначений регулярных выражений и расширенной формы Бэкуса-Наура . Он описывает синтаксис S-выражений , синтаксис данных языка программирования Lisp , который определяет продукции для синтаксических категорий выражение , атом , число , символ и список :

expression = atom   | list
atom       = number | symbol    
number     = [+-]?['0'-'9']+
symbol     = ['A'-'Z']['A'-'Z''0'-'9'].*
list       = '(', expression*, ')'

Эта грамматика определяет следующее:

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

Здесь десятичные цифры, символы верхнего и нижнего регистра и круглые скобки являются терминальными символами.

Ниже приведены примеры правильно сформированных последовательностей токенов в этой грамматике: ' 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->real и p->im не имеют смысла):

 complex *p = NULL;
 complex abs_p = sqrt (p->real * p->real + p->im * p->im);

В качестве более простого примера,

 int x;
 printf("%d", x);

синтаксически допустим, но не определен семантически, поскольку использует неинициализированную переменную . Несмотря на то, что компиляторы некоторых языков программирования (например, Java и C#) обнаруживают ошибки неинициализированных переменных такого типа, их следует рассматривать как семантические ошибки, а не синтаксические ошибки. ^[6]^[13]

См. также

Чтобы быстро сравнить синтаксис различных языков программирования, взгляните на список «Hello, World!» примеры программ :

Ссылки

^ Jump up to: ^а ^б Фридман, Дэниел П.; Митчелл Ванд; Кристофер Т. Хейнс (1992). Основы языков программирования (1-е изд.). Массачусетский технологический институт Пресс. ISBN 0-262-06145-7 .
^ Смит, Деннис (1999). Проектирование поддерживаемого программного обеспечения . Springer Science & Business Media.
^ Пай, Вайкунта; Айтал, PS (31 декабря 2020 г.). «Систематический обзор литературы по методам реализации лексического анализатора при проектировании компилятора» . Международный журнал прикладной инженерии и менеджмента (IJAEML) . 4 (2): 285–301. ISSN 2581-7000 .
^ Ахо, Альфред В.; Моника С. Лам; Рави Сетхи; Джеффри Д. Уллман (2007). Составители: принципы, методы и инструменты (2-е изд.). Эддисон Уэсли. ISBN 0-321-48681-1 . Раздел 4.1.3: Обработка синтаксических ошибок, стр. 194–195.
^ Лауден, Кеннет К. (1997). Создание компилятора: принципы и практика . Брукс/Коул. ISBN 981-243-694-4 . Упражнение 1.3, стр. 27–28.
^ Jump up to: ^а ^б Семантические ошибки в Java
^ Jump up to: ^а ^б ^с Слонеггер, Кеннет; Курц, Барри (1995). Формальный синтаксис и семантика языков программирования . Издательская компания Аддисон-Уэсли . ISBN 0-201-65697-3 .
^ Майкл Сипсер (1997). «2.2 Автоматы с выталкиванием». Введение в теорию вычислений . Издательство ПВС. стр. 101–114. ISBN 0-534-94728-Х .
^ Комментарий LtU, поясняющий, что неразрешимой проблемой является принадлежность к классу программ Perl.
^ хроматический пример кода Perl, который выдает синтаксическую ошибку в зависимости от значения случайной величины.
^ «Введение в макросы Common Lisp» . Apl.jhu.edu. 8 февраля 1996 г. Архивировано из оригинала 6 августа 2013 г. Проверено 17 августа 2013 г.
^ «Поваренная книга Common Lisp — макросы и обратные кавычки» . Cl-cookbook.sourceforge.net. 16 января 2007 г. Проверено 17 августа 2013 г.
^ Проблема синтаксиса или семантики?

Внешние ссылки

Различные синтаксические конструкции, используемые в языках программирования.
Ошибка Python «Ошибка импорта: модуль не назван». Почему? Как? Командная строка? [Решено в 2021 году]

[eopl-1] Jump up to: ^а ^б Фридман, Дэниел П.; Митчелл Ванд; Кристофер Т. Хейнс (1992). Основы языков программирования (1-е изд.). Массачусетский технологический институт Пресс. ISBN 0-262-06145-7 .

[2] Смит, Деннис (1999). Проектирование поддерживаемого программного обеспечения . Springer Science & Business Media.

[3] Пай, Вайкунта; Айтал, PS (31 декабря 2020 г.). «Систематический обзор литературы по методам реализации лексического анализатора при проектировании компилятора» . Международный журнал прикладной инженерии и менеджмента (IJAEML) . 4 (2): 285–301. ISSN 2581-7000 .

[4] Ахо, Альфред В.; Моника С. Лам; Рави Сетхи; Джеффри Д. Уллман (2007). Составители: принципы, методы и инструменты (2-е изд.). Эддисон Уэсли. ISBN 0-321-48681-1 . Раздел 4.1.3: Обработка синтаксических ошибок, стр. 194–195.

[5] Лауден, Кеннет К. (1997). Создание компилятора: принципы и практика . Брукс/Коул. ISBN 981-243-694-4 . Упражнение 1.3, стр. 27–28.

[uninitialized_var-6] Jump up to: ^а ^б Семантические ошибки в Java

[:0-7] Jump up to: ^а ^б ^с Слонеггер, Кеннет; Курц, Барри (1995). Формальный синтаксис и семантика языков программирования . Издательская компания Аддисон-Уэсли . ISBN 0-201-65697-3 .

[8] Майкл Сипсер (1997). «2.2 Автоматы с выталкиванием». Введение в теорию вычислений . Издательство ПВС. стр. 101–114. ISBN 0-534-94728-Х .

[9] Комментарий LtU, поясняющий, что неразрешимой проблемой является принадлежность к классу программ Perl.

[10] хроматический пример кода Perl, который выдает синтаксическую ошибку в зависимости от значения случайной величины.

[11] «Введение в макросы Common Lisp» . Apl.jhu.edu. 8 февраля 1996 г. Архивировано из оригинала 6 августа 2013 г. Проверено 17 августа 2013 г.

[12] «Поваренная книга Common Lisp — макросы и обратные кавычки» . Cl-cookbook.sourceforge.net. 16 января 2007 г. Проверено 17 августа 2013 г.

[13] Проблема синтаксиса или семантики?

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]