Грамматика Ван Вейнгаардена

В информатике — грамматика Ван Вейнгаардена (также vW-грамматика или W-грамматика). ^[1]) — формализм для определения формальных языков . Название происходит от формализма, изобретенного Адрианом ван Вейнгаарденом. ^[2]с целью определения АЛГОЛ 68 языка программирования . Полученная спецификация ^[3] остается его наиболее заметным применением.

Грамматики Ван Вейнгаардена решают проблему, заключающуюся в том, что контекстно-свободные грамматики не могут выражать согласие или ссылку, когда две разные части предложения должны каким-то образом согласовываться друг с другом. Например, предложение «Птицы ели» не является стандартным английским языком, поскольку в нем не согласовывается число . Контекстно-свободная грамматика будет анализировать фразы «Птицы ели», «Птицы ели» и «Птица ела» одинаково. Однако преимуществом контекстно-свободных грамматик является простота, тогда как грамматики Ван Вейнгаардена считаются очень сложными. ^[4]

Два уровня [ править ]

W-грамматики — это двухуровневые грамматики : они определяются парой грамматик, которые работают на разных уровнях:

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

Набор строк, генерируемых W-грамматикой, определяется двухэтапным процессом:

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

Согласованная замена, используемая на первом этапе, аналогична замене в логике предикатов и фактически поддерживает логическое программирование ; это соответствует унификации в Прологе , как заметил Ален Кольмерауэр ^{[ где? ]}.

W-грамматики полны по Тьюрингу ; ^[5] следовательно, все проблемы принятия решений, касающиеся языков, которые они генерируют, таких как

генерирует ли W-грамматика заданную строку
генерирует ли W-грамматика вообще никаких строк

неразрешимы .

Сокращенные варианты, известные как аффиксные грамматики , были разработаны и применены при построении компиляторов и для описания естественных языков.

Программы определенной логики , то есть логические программы, не использующие отрицание, можно рассматривать как подкласс W-грамматик. ^[6]

Мотивация и история [ править ]

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

Эта работа повлияла на разработку и реализацию языков программирования , в первую очередь на АЛГОЛ 60 , который представил синтаксическое описание в форме Бэкуса-Наура .

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

Их можно легко выразить в W-грамматиках. (См. пример ниже.)

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

Переменная должна быть инициализирована до использования ее значения.
В строго типизированных языках каждой переменной присваивается тип, и все использования переменной должны соответствовать ее типу.
Часто его тип необходимо явно объявить перед использованием.

W-грамматики основаны на идее предоставления нетерминальным символам контекстно-свободных грамматик атрибутов (или аффиксов ), которые передают информацию между узлами дерева разбора , используемых для ограничения синтаксиса и определения семантики.

Эта идея была хорошо известна в то время; например, Дональд Кнут посетил комитет по проектированию Алгола 68, разрабатывая свою собственную версию — грамматики атрибутов . ^[7]

Дополняя описание синтаксиса атрибутами, можно проверить ограничения, подобные приведенным выше, исключая многие недопустимые программы во время компиляции. Как писал Ван Вейнгаарден в своем предисловии: ^[2]

Моими главными возражениями были наверняка ненужные мне ограничения и определение синтаксиса и семантики. На самом деле синтаксис, рассматриваемый в MR 75, создает большое количество программ, тогда как я бы предпочел иметь как можно большее подмножество значимых программ, что требует более строгого синтаксиса. [...] вскоре стало ясно, что некоторые более эффективные инструменты, чем нотация Бэкуса, могут быть выгодными [...]. Я разработал схему [...], которая позволяет конструкции языка нести в синтаксисе гораздо больше информации, чем обычно.

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

После их представления в «Заключительном отчете» АЛГОЛА 68 1968 года W-грамматики считались слишком мощными и неограниченными, чтобы быть практичными. ^{[ нужна цитата ]}

Частично это было следствием того, как они применялись; «Пересмотренный отчет» Алгола 68 1973 года содержит гораздо более удобочитаемую грамматику без изменения самого формализма W-грамматики.

Между тем, стало ясно, что W-грамматики, когда они используются во всей своей общности, действительно слишком мощны для таких практических целей, как использование входных данных для генератора синтаксического анализатора . Они описывают в точности все рекурсивно перечислимые языки . ^[8] является неразрешимой проблемой что делает синтаксический анализ невозможным в целом: решить, может ли данная строка быть сгенерирована данной W-грамматикой, .

Следовательно, их использование должно быть серьезно ограничено при автоматическом синтаксическом анализе или переводе. Для решения этой проблемы были разработаны ограниченные и модифицированные варианты W-грамматик, например

Расширенные аффиксные грамматики (EAG), применяемые для описания грамматик естественного языка, такого как английский и испанский);
Q-системы , также применяемые для обработки естественного языка;
языков построения серия языков CDL, применяемая в качестве компиляторов для языков программирования .

После 1970-х годов интерес к этому подходу угас; время от времени публикуются новые исследования. ^[9]

Примеры [ править ]

Соглашение в английской грамматике [ править ]

В английском языке существительные, местоимения и глаголы имеют такие атрибуты, как грамматическое число , род и лицо , которые должны согласовываться между подлежащим , основным глаголом и местоимениями, относящимися к предмету:

Я моюсь.
Она моется сама.
Мы моемся.

являются действительными предложениями; недействительными являются, например:

*Я умываюсь.
*Она моется.
*Мыемся.

Здесь соглашение служит для того, чтобы подчеркнуть, что оба местоимения (например, я и я ) относятся к одному и тому же человеку.

Контекстно-свободная грамматика для генерации всех таких предложений:

<предложение> ::= <подлежащее> <глагол> <объект>
 <субъект> ::= Я |  Вы |  Он |  Она |  Мы |  Они
 <глагол> ::= мыть |  моет
 <объект> ::= я |  себя |  сам |  сама |  мы сами |  себя |  сами себя

Из предложения мы можем сгенерировать все комбинации:

я моюсь
 я умываюсь
 я моюсь сам
 [...]
 Они моются
 Они моются

W-грамматика для генерации только допустимых предложений:

<предложение <НОМЕР> <ПОЛ> <ЧЕЛОВЕК>>
   ::= <субъект <НОМЕР> <ПОЛ> <ЧЕЛОВЕК>>
       <глагол <НОМЕР> <ЧЕЛОВЕК>>
       <объект <НОМЕР> <ПОЛ> <ЧЕЛОВЕК>>

<субъект в единственном числе <ПОЛ> 1-й> ::= I
 <субъект <НОМЕР> <ПОЛ> 2-й> ::= Вы
 <субъект в единственном числе, третий мужчина> ::= Он
 <субъект в единственном числе, женский 3-й> ::= Она
 <подлежащее множественного числа <ПОЛ> 1-й> ::= Мы
 <субъект в единственном числе <ПОЛ> 3-й> ::= Они

<глагол первого числа единственного числа> ::= мыть
 <глагол 2-го числа единственного числа> ::= мыть
 <глагол 3-го числа единственного числа> ::= моет
 <глагол множественного числа <ЛИЦО>> ::= мыть

<объект единственного числа <ПОЛ> 1-й> ::= я
 <объект единственного числа <ПОЛ> 2-й> ::= вы
 <объект единственного числа, 3-й мужчина> ::= сам
 <объект единственного числа, женский 3-й> ::= сама
 <объект множественного числа <ПОЛ> 1-й> ::= мы сами
 <объект множественного числа <ПОЛ> 2-й> ::= вы сами
 <объект множественного числа <ПОЛ> 3-й> ::= сами

<НОМЕР> ::== единственное число |  множественное число
 <ПОЛ> ::== мужской |  женский
 <ЧЕЛОВЕК> ::== 1-й |  2-й |  3-й

Стандартный неконтекстно-свободный язык [ править ]

Хорошо известен неконтекстно-свободный язык.

\{a^{n}b^{n}a^{n}|n\geq 1\}.

Двухуровневая грамматика этого языка — метаграмматика.

Н ::= 1 | N1

X ::= а | б

вместе с грамматической схемой

Начало ::=

\langle a^{N}\rangle \langle b^{N}\rangle \langle a^{N}\rangle

\langle X^{N1}\rangle

::=

\langle X^{N}\rangle X

\langle X^{1}\rangle

::= Х

Требование допустимого использования переменных в ALGOL [ править ]

Пересмотренный отчет об алгоритмическом языке Алгол 60 ^[10] определяет полный контекстно-свободный синтаксис языка.

Назначения определяются следующим образом (раздел 4.2.1):

<левая часть>
   ::= <переменная> :=
     |  <идентификатор процедуры> :=

 <левый список деталей>
   ::= <левая часть>
     |  <список левой части> <левая часть>

 <оператор присвоения>
   ::= <список левой части> <арифметическое выражение>
     |  <список левой части> <логическое выражение>

<Переменная> может быть (помимо прочего) <идентификатором>, который, в свою очередь, определяется как:

<идентификатор> ::= <буква> |  <идентификатор> <буква> |  <идентификатор> <цифра>

Примеры (раздел 4.2.2):

s:=p[0]:=n:=n+1+s
n:=n+1
A:=B/C-v-q×S
S[v,k+2]:=3-arctan(sTIMESzeta)
V:=Q>Y^Z

Выражения и присваивания должны быть проверены по типу : например,

в n:=n+1 n должно быть числом (целым или вещественным);
в A:=B/Cvq×S все переменные должны быть числами;
в V:=Q>Y^Z все переменные должны иметь тип Boolean.

Приведенные выше правила различают <арифметическое выражение> и <логическое выражение>, но они не могут гарантировать, что одна и та же переменная всегда имеет один и тот же тип.

Это (неконтекстно-свободное) требование можно выразить в W-грамматике, аннотируя правила атрибутами, которые записывают для каждой используемой или присвоенной переменной ее имя и тип.

Эту запись затем можно перенести во все места грамматики, где необходимо сопоставить типы, и реализовать проверку типов.

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

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

<левая часть с <TYPED> <NAME>>
   ::= <переменная с <TYPED> <NAME>> :=
     |  <идентификатор процедуры с <TYPED> <NAME>> :=

 <список левой части <TYPEMAP1>>
   ::= <левая часть с <TYPED> <NAME>>
       <где <TYPEMAP1> — это <TYPED> <NAME> добавлено в отсортированный <EMPTY>>
     |  <список левой части <TYPEMAP2>>
       <левая часть с <ТИПОМ> <ИМЯ>>
       <где <TYPEMAP1> — это <TYPED> <NAME> добавлено к отсортированному <TYPEMAP2>>

 <оператор присваивания <ASSIGNED TO> <USED>>
   ::= <список левой части <НАЗНАЧЕНО>> <арифметическое выражение <ИСПОЛЬЗУЕТСЯ>>
     |  <список левой части <НАЗНАЧЕНО>> <Логическое выражение <ИСПОЛЬЗУЕТСЯ>>

 <где <TYPED> <NAME> — это <TYPED> <NAME> добавлено к отсортированному <EMPTY>>
   "="

 <где <TYPEMAP1> — это <TYPED1> <NAME1> добавлен к отсортированному <TYPEMAP2>>
   ::= <где <TYPEMAP2> — это <TYPED2> <NAME2> добавлен к отсортированному <TYPEMAP3>>
       <где <ИМЯ1> лексикографически предшествует <ИМЯ2>>

 <где <TYPEMAP1> — это <TYPED1> <NAME1> добавлен к отсортированному <TYPEMAP2>>
   ::= <где <TYPEMAP2> — это <TYPED2> <NAME2> добавлен к отсортированному <TYPEMAP3>>
       <где <ИМЯ2> лексикографически предшествует <ИМЯ1>>
       <где <TYPEMAP3> — это <TYPED1> <NAME1> добавлен к отсортированному <TYPEMAP4>>

 <где <EMPTY> лексикографически стоит перед <NAME1>>
   ::= <где <ИМЯ1> — это <БУКВА ИЛИ ЦИФРА>, за которым следует <ИМЯ2>>
 
 <где <ИМЯ1> лексикографически предшествует <ИМЯ2>>
   ::= <где <ИМЯ1> — это <БУКВА ИЛИ ЦИФРА>, за которым следует <ИМЯ3>>
       <где <ИМЯ2> — это <БУКВА ИЛИ ЦИФРА>, за которым следует <ИМЯ4>>
       <где <ИМЯ3> лексикографически предшествует <ИМЯ4>>

 <где <ИМЯ1> лексикографически предшествует <ИМЯ2>>
   ::= <где <ИМЯ1> — это <БУКВА ИЛИ ЦИФРА 1>, за которой следует <ИМЯ3>>
       <где <ИМЯ2> — это <БУКВА ИЛИ ЦИФРА 2>, за которой следует <ИМЯ4>>
       <где <БУКВА ИЛИ ЦИФРА 1> предшествует+ <БУКВА ИЛИ ЦИФРА 2>

 <где <БУКВА ИЛИ ЦИФРА 1> предшествует+ <БУКВА ИЛИ ЦИФРА 2>
   ::= <где <БУКВА ИЛИ ЦИФРА 1> предшествует <БУКВА ИЛИ ЦИФРА 2>

 <где <БУКВА ИЛИ ЦИФРА 1> предшествует+ <БУКВА ИЛИ ЦИФРА 2>
   ::= <где <БУКВА ИЛИ ЦИФРА 1> предшествует+ <БУКВА ИЛИ ЦИФРА 3>
       <где <БУКВА ИЛИ ЦИФРА 3> предшествует+ <БУКВА ИЛИ ЦИФРА 2>

 <где a предшествует b> :==
 <где b предшествует c> :==
 [...]

 <TYPED> ::== реальный |  целое число |  логическое значение

 <ИМЯ> ::== <БУКВА> |  <ИМЯ> <БУКВА> |  <ИМЯ> <ЦИФРА>
 <БУКВА ИЛИ ЦИФРА> ::== <БУКВА> |  <ЦИФРА>
 <БУКВА ИЛИ ЦИФРА 1> ::= <БУКВА ИЛИ ЦИФРА>
 <БУКВА ИЛИ ЦИФРА 2> ::= <БУКВА ИЛИ ЦИФРА>
 <БУКВА ИЛИ ЦИФРА 3> ::= <БУКВА ИЛИ ЦИФРА>
 <БУКВА> ::== а |  б |  с |  [...]
 <ЦИФРА> ::== 0 |  1 |  2 |  [...]

 <ИМЯ1> ::== <ИМЯ>
 <ИМЯ2> ::== <ИМЯ>
 <НАЗНАЧЕНО> ::== <ИМЯ>
 <ИСПОЛЬЗУЕТСЯ> ::== <ИМЯ>
 <ИМЯ> ::== <ИМЯ> |  <ИМЯ> <ИМЯ>

 <ПУСТОЕ> ::==
 <TYPEMAP> ::== (<TYPED> <NAME>) <TYPEMAP>
 <TYPEMAP1> ::== <TYPEMAP>
 <TYPEMAP2> ::== <TYPEMAP>
 <TYPEMAP3> ::== <TYPEMAP>

По сравнению с исходной грамматикой были добавлены три новых элемента:

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

Новые гиперправила $\epsilon$ -rules: они генерируют только пустую строку.

Примеры Алгола 68 [ править ]

В отчетах ALGOL 68 используются немного другие обозначения без <угловых скобок>.

как в Заключительном отчете 1968 §2.1 года АЛГОЛ 68 ,

а) программа: открытый символ, стандартная прелюдия,
       опция прелюдии библиотеки, конкретная программа, выход,
       опция библиотечной постлюдии, стандартная постлюдия, символ закрытия.
  б) стандартная прелюдия: последовательность прелюдии объявления.
  в) прелюдия библиотеки: последовательность прелюдии объявления.
  г) конкретная программа:
       опция последовательности меток, строгое условие CLOSED void.
  e) выход: символ перехода, буква e, буква x, буква i, буква t, символ метки.
  е) библиотечная постлюдия: констатационная интерлюдия.
  ж) стандартная постлюдия: сильная последовательность недействительных предложений

АЛГОЛ 68, как в пересмотренном отчете 1973 г. §2.2.1, §10.1.1 [ править ]

программа: Strong void новое закрытое предложение

  А) ВНЕШНИЙ:: стандартный;  библиотека;  система ;  особый.
  Б) СТОП:: метка буква s буква т буква о буква р.

  а) текст программы: токен начала STYLE, новые прелюдии LAYER1, 
         параллельный токен, новый ПАКЕТ задач LAYER1, 
         Конечный токен STYLE.
  б) Прелюдии NEST1: стандартная прелюдия NEST1 с DECS1, 
         Прелюдия библиотеки NEST1 к DECSETY2, 
         Прелюдия системы NEST1 с DECSETY3, где (NEST1) —
         (новый ПУСТОЙ новый DECS1 DECSETY2 DECSETY3).
  в) Прелюдия NEST1 EXTERNAL с DECSETY1: 
         сильная пустота серии NEST1 с DECSETY1, переходим к токену; 
         где (DECSETY1) — (ПУСТОЙ), ПУСТОЙ.
  г) Задачи NEST1: список системных задач NEST1, а также токен, 
         Список пакетов задач пользователя NEST1.
  д) Системная задача NEST1: сильная пустота блока NEST1.
  f) Задача пользователя NEST1: конкретная прелюдия NEST2 с DECS, 
         NEST2 конкретный пакет программ, переход на токен, 
         NEST2 конкретная постлюдия, 
         где (NEST2) — (NEST1 новая DECS STOP).
  g) Конкретная программа NEST2: 
         NEST2 новое объединенное определение метки LABSETY3
         LABSETY3, сильная пустота NEST2, новый LABSETY3
         ЗАКРЫТОЕ положение.
  h) Определение объединенной метки NEST LABSETY: 
         где (LABSETY) — (ПУСТОЙ), ПУСТОЙ ; 
         где (LABSETY) — это (LAB1 LABSETY1), 
            Определение метки NEST LAB1, 
            NEST присоединился к определению метки $ LABSETY1. 
  i) Конкретный постлюд NEST2:
         сильная пустота серии NEST2 со СТОПом.

Простым примером возможностей W-грамматик является предложение

а) текст программы: токен начала STYLE, новые прелюдии LAYER1, 
        параллельный токен, новый ПАКЕТ задач LAYER1, 
        Конечный токен STYLE.

Это позволяет использовать BEGIN ... END и { } в качестве разделителей блоков, исключая при этом BEGIN ... } и { ... END.

Можно сравнить грамматику в отчете с анализатором Yacc для подмножества АЛГОЛА 68 Марка ван Леувена. ^[11]

Реализации [ править ]

Энтони Фишер написал йо-йо , ^[12] синтаксический анализатор большого класса W-грамматик с примерами грамматик для ( стандарт фактический 7185 ISO для выражений eva, sal и Pascal Pascal использует расширенную форму Бэкуса-Наура ).

Дик Грюн создал программу на языке C , которая генерировала все возможные варианты W-грамматики. ^[13]

Приложения вне ALGOL 68 [ править ]

Упомянутые выше применения расширенных аффиксных грамматик (EAG) можно эффективно рассматривать как приложения W-грамматик, поскольку EAG очень близки к W-грамматикам. ^[14]

W-грамматики также были предложены для описания сложных действий человека в эргономике . ^{[ нужна цитата ]}

также предоставлено описание W-грамматики Для Ada . ^[15]

См. также [ править ]

Ссылки [ править ]

^ Кливленд, Дж. Крейг; Узгалис, Роберт К. (1977). Грамматики языков программирования . Эльзевир. ISBN 978-0-444-00199-3 .
^ Перейти обратно: ^а ^б ван Вейнгаарден, Адриан (4 апреля 1972 г.) [Преждевременное и предварительное издание 22 октября 1965 г.]. MR 76: Ортогональный дизайн и описание формального языка (PDF) (Технический отчет). Амстердам: КРИ . Архивировано из оригинала (PDF) 2 октября 2017 г.
^ ван Вейнгаарден, А.; и другие. (ред.). «Пересмотренный отчет об алгоритмическом языке АЛГОЛ 68» . Архивировано из оригинала 24 января 2002 года.
^ Костер, ЦДХ (1996). «Создание Алгола 68». В Бьёрнере, Д; Брой, М.; Поттосин И.В. (ред.). Перспективы системной информатики . Конспекты лекций по информатике. Том. 1181. Берлин: Шпрингер. стр. 55–67. дои : 10.1007/3-540-62064-8_6 . ISBN 978-3-540-62064-8 .
^ Синцов, М. (1967). «Существование синтаксиса Ван Вейнгаардена для каждого рекурсивно перечислимого множества». Анналы Брюссельского научного общества . 2 : 115–118.
^ Дерансар, Пьер; Малушинский, Январь (1993), «Грамматические расширения логических программ» , «Грамматический взгляд на логическое программирование », The MIT Press, стр. 109–140, doi : 10.7551/mitpress/3345.003.0008 , ISBN 9780262290845 , получено 14 июня 2023 г.
^ Кнут, Дональд Э. (1990), «Происхождение грамматик атрибутов» ( Plain TeX , gZiped ) , Материалы Международной конференции по грамматикам атрибутов и их применениям , Springer Verlag : 1–12 .
^ Синцов, М. (1967). «Существование синтаксиса Ван Вейнгаардена для каждого рекурсивно перечислимого множества». Анналы Брюссельского научного общества . 81 : 115–118.
^ Аугусто, LM (2023). «Двухуровневые грамматики: некоторые интересные свойства грамматик Ван Вейнгаардена» (PDF) . Омега - Журнал формальных языков . 1 :3–34.
^ Бэкус, Дж.В.; и другие. (1963). «Доработанный отчет по алгоритмическому языку АЛГОЛ 60» . Компьютерный журнал . 5 (4): 349–367. дои : 10.1093/comjnl/5.4.349 .
^ «Синтаксис», Алгол 68 , FR : Univ Poitiers
^ Фишер, Энтони, «йо-йо», Программное обеспечение , Великобритания : Йорк .
^ Грюн, Дик, Генератор двухуровневых предложений , Нидерланды : VU .
^ Альблас, Хенк; Меличар, Боривой (1991). Атрибутные грамматики, приложения и системы . Конспекты лекций по информатике. Том. 545. Спрингер. п. 371. ИСБН 978-3540545729 .
^ Флауэрс, Рой, Описание W-грамматики для Ады (PDF) (магистерская диссертация), Технологический институт ВВС, Авиационный университет

Дальнейшее чтение [ править ]

Аугусто, LM (2023). «Грамматики ван Вейнгаардена: учебник синтаксиса с разрешимыми ограничениями» (PDF) . Журнал структур и систем знаний . 4 : 1–39.
Пембертон, Стивен (2016) [1982]. «Исполняемое семантическое определение языков программирования с использованием двухуровневых грамматик (грамматики Ван Вейнгаардена)» . Амстердам: Центр математики и информатики. .
Петерссон, Кент (1990). «Синтаксис и семантика языков программирования» (PDF) . Черновые конспекты лекций . Архивировано из оригинала (PDF) 5 июня 2001 года.

[1] Кливленд, Дж. Крейг; Узгалис, Роберт К. (1977). Грамматики языков программирования . Эльзевир. ISBN 978-0-444-00199-3 .

[mr76-2] Перейти обратно: ^а ^б ван Вейнгаарден, Адриан (4 апреля 1972 г.) [Преждевременное и предварительное издание 22 октября 1965 г.]. MR 76: Ортогональный дизайн и описание формального языка (PDF) (Технический отчет). Амстердам: КРИ . Архивировано из оригинала (PDF) 2 октября 2017 г.

[3] ван Вейнгаарден, А.; и другие. (ред.). «Пересмотренный отчет об алгоритмическом языке АЛГОЛ 68» . Архивировано из оригинала 24 января 2002 года.

[4] Костер, ЦДХ (1996). «Создание Алгола 68». В Бьёрнере, Д; Брой, М.; Поттосин И.В. (ред.). Перспективы системной информатики . Конспекты лекций по информатике. Том. 1181. Берлин: Шпрингер. стр. 55–67. дои : 10.1007/3-540-62064-8_6 . ISBN 978-3-540-62064-8 .

[5] Синцов, М. (1967). «Существование синтаксиса Ван Вейнгаардена для каждого рекурсивно перечислимого множества». Анналы Брюссельского научного общества . 2 : 115–118.

[6] Дерансар, Пьер; Малушинский, Январь (1993), «Грамматические расширения логических программ» , «Грамматический взгляд на логическое программирование », The MIT Press, стр. 109–140, doi : 10.7551/mitpress/3345.003.0008 , ISBN 9780262290845 , получено 14 июня 2023 г.

[7] Кнут, Дональд Э. (1990), «Происхождение грамматик атрибутов» ( Plain TeX , gZiped ) , Материалы Международной конференции по грамматикам атрибутов и их применениям , Springer Verlag : 1–12 .

[8] Синцов, М. (1967). «Существование синтаксиса Ван Вейнгаардена для каждого рекурсивно перечислимого множества». Анналы Брюссельского научного общества . 81 : 115–118.

[9] Аугусто, LM (2023). «Двухуровневые грамматики: некоторые интересные свойства грамматик Ван Вейнгаардена» (PDF) . Омега - Журнал формальных языков . 1 :3–34.

[10] Бэкус, Дж.В.; и другие. (1963). «Доработанный отчет по алгоритмическому языку АЛГОЛ 60» . Компьютерный журнал . 5 (4): 349–367. дои : 10.1093/comjnl/5.4.349 .

[11] «Синтаксис», Алгол 68 , FR : Univ Poitiers

[yo-yo-12] Фишер, Энтони, «йо-йо», Программное обеспечение , Великобритания : Йорк .

[13] Грюн, Дик, Генератор двухуровневых предложений , Нидерланды : VU .

[14] Альблас, Хенк; Меличар, Боривой (1991). Атрибутные грамматики, приложения и системы . Конспекты лекций по информатике. Том. 545. Спрингер. п. 371. ИСБН 978-3540545729 .

[15] Флауэрс, Рой, Описание W-грамматики для Ады (PDF) (магистерская диссертация), Технологический институт ВВС, Авиационный университет

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]