stringtranslate.com

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

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

Грамматики Ван Вейнгаардена решают проблему, заключающуюся в том, что контекстно-свободные грамматики не могут выражать согласие или ссылку, когда две разные части предложения должны каким-то образом согласовываться друг с другом. Например, предложение «The birds was eating» не является стандартным английским , потому что в нем не согласуется число . Контекстно-свободная грамматика анализировала бы «The birds was eating» и «The birds were eating» и «The bird was eating» одинаково. Однако контекстно-свободные грамматики имеют преимущество простоты, тогда как грамматики Ван Вейнгаардена считаются очень сложными. [4]

Два уровня

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

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

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

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

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

являются неразрешимыми .

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

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

Мотивация и история

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

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

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

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

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

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

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

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

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

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

После их введения в «Заключительном отчете» ALGOL 68 1968 года W-грамматики широко рассматривались как слишком мощные и не имеющие ограничений для практического применения. [ необходима цитата ]

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

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

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

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

Примеры

Согласование в английской грамматике

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

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

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

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

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

Из <sentence>, мы можем сгенерировать все комбинации:

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

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

<предложение < НОМЕР >  < ПОЛ >  < ЛИЦО > > ::= <тема < НОМЕР >  < ПОЛ >  < ЛИЦО > > <глагол < ЧИСЛО >  < ЛИЦО > > <объект < НОМЕР >  < ПОЛ >  < ЛИЦО > > <субъект единственное число < ПОЛ > 1-й> ::= Я <субъект < НОМЕР >  < ПОЛ > 2-й> ::= Ты < субъект единственное число мужской 3-й >  ::= Он < субъект единственное число женский 3-й >  ::= Она <субъект множественного числа < РОD > 1-й> ::= Мы <субъект единственное число < ПОЛ > 3-й> ::= Они < глагол единственного числа 1-й >  ::= мыть < глагол единственного числа 2-й >  ::= мыть < глагол единственного числа 3-й >  ::= стирает <глагол множественное число < ЛИЦО > > ::= мыть <объект единственное число < ПОЛ > 1-й> ::= я сам <объект единственного числа < ПОЛ > 2-й> ::= вы сами < объект единственного числа мужской 3-й >  ::= он сам < объект единственного числа женский 3-й >  ::= она сама <объект множественного числа < ПОЛ > 1-й> ::= мы сами <объект множественного числа < РОДА > 2-й> ::= вы сами <объект множественного числа < ПОЛ > 3-й> ::= сами < ЧИСЛО >  ::= = единственное число | множественное число < ПОЛ >  ::= = мужской | женский < ЛИЦО >  ::= = 1-й | 2-й | 3-й

Стандартный неконтекстно-свободный язык

Известный неконтекстно-свободный язык — это

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

Н ::= 1 | Н1
Х ::= а | б

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

Начало ::= ⟨a N ⟩ ⟨b N ⟩ ⟨a N ⟩
⟨X N1 ⟩  ::= ⟨X N ⟩ X
⟨X 1 ⟩  ::= X

Вопросы. Если заменить N1 на новую букву, скажем C, то язык, порожденный грамматикой, сохраняется? Или N1 следует читать как строку из двух символов, то есть N, за которой следует 1? Конец вопросов.


Требование допустимого использования переменных в АЛГОЛ

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

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

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

A <variable>может быть (помимо прочего) <identifier>, что в свою очередь определяется как:

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

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

с:=р[0]:=n:=n+1+sн:=н+1А:=B/Cvq×SS[v,k+2]:=3-arctan(sTIMESzeta)В:=Q>Y^Z

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

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

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

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

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

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

<левая часть с < ТИПИРОВАННЫМ >  < ИМЯ > > ::= <переменная с < ТИПИРОВАННЫМ >  < ИМЯ > > := | <идентификатор процедуры с < ТИПИРОВАННЫМ >  < ИМЯ > > :=  <список левой части < TYPEMAP1 > > ::= <левая часть с < TYPED >  < NAME > > <где < TYPEMAP1 > - это < TYPED >  < NAME > , добавленный к отсортированному < EMPTY > > | <список левой части < TYPEMAP2 > > <левая часть с < НАБРАНО >  < ИМЯ > > <где < TYPEMAP1 > - это < TYPED >  < NAME > , добавленный к отсортированному < TYPEMAP2 > >  <оператор присваивания < НАЗНАЧЕНО >  < ИСПОЛЬЗУЕТСЯ > > ::= <список левой части < НАЗНАЧЕНО > > <арифметическое выражение < ИСПОЛЬЗУЕТСЯ > > | <список левой части < НАЗНАЧЕНО > > <Булево выражение < ИСПОЛЬЗУЕТСЯ > >  <где < ТИПИРОВАНО >  < ИМЯ > < ТИПИРОВАНО > < ИМЯ > добавлено к отсортированному < ПУСТО > > :: =   <где < TYPEMAP1 > - это < TYPED1 >  < NAME1 > , добавленный к отсортированному < TYPEMAP2 > > ::= <где < TYPEMAP2 > - это < TYPED2 >  < NAME2 >, добавленный к отсортированному < TYPEMAP3 > > <где < NAME1 > лексикографически стоит перед < NAME2 > >  <где < TYPEMAP1 > - это < TYPED1 >  < NAME1 > , добавленный к отсортированному < TYPEMAP2 > > ::= <где < TYPEMAP2 > - это < TYPED2 >  < NAME2 >, добавленный к отсортированному < TYPEMAP3 > > <где < NAME2 > лексикографически стоит перед < NAME1 > > <где < TYPEMAP3 > - это < TYPED1 >  < NAME1 >, добавленный к отсортированному < TYPEMAP4 > >  <где < ПУСТО > лексикографически стоит перед < ИМЯ1 > > ::= <где < ИМЯ1 > это < БУКВА ИЛИ ЦИФРА >, за которой следует < ИМЯ2 > >  <где < NAME1 > лексикографически стоит перед < NAME2 > > ::= <где < NAME1 > это < БУКВА ИЛИ ЦИФРА >, за которой следует < NAME3 > > <где < ИМЯ2 > - это < БУКВА ИЛИ ЦИФРА >, за которой следует < ИМЯ4 > > <где < NAME3 > лексикографически стоит перед < NAME4 > >  <где < NAME1 > лексикографически стоит перед < NAME2 > > ::= <где < NAME1 > это < БУКВА ИЛИ ЦИФРА 1 >, за которой следует < NAME3 > > <где < ИМЯ2 > это < БУКВА ИЛИ ЦИФРА 2 >, за которой следует < ИМЯ4 > > <где < БУКВА ИЛИ ЦИФРА 1 > предшествует+ < БУКВА ИЛИ ЦИФРА 2 >  <где < БУКВА ИЛИ ЦИФРА 1 > предшествует + < БУКВА ИЛИ ЦИФРА 2 >  ::= <где < БУКВА ИЛИ ЦИФРА 1 > предшествует < БУКВА ИЛИ ЦИФРА 2 >  <где < БУКВА ИЛИ ЦИФРА 1 > предшествует+ < БУКВА ИЛИ ЦИФРА 2 >  ::= <где < БУКВА ИЛИ ЦИФРА 1 > предшествует+ < БУКВА ИЛИ ЦИФРА 3 > <где < БУКВА ИЛИ ЦИФРА 3 > предшествует+ < БУКВА ИЛИ ЦИФРА 2 >  < где a предшествует b >  :== < где b предшествует c >  :== [...]  < ТИПИРОВАНО >  ::= = вещественное | целое | логическое  < ИМЯ >  ::= = < БУКВА > | < ИМЯ >  < БУКВА > | < ИМЯ >  < ЦИФРА >  < БУКВА ИЛИ ЦИФРА >  ::= = < БУКВА > | < ЦИФРА >  < БУКВА ИЛИ ЦИФРА 1 >  ::=  < БУКВА ИЛИ ЦИФРА >  < БУКВА ИЛИ ЦИФРА 2 >  ::=  < БУКВА ИЛИ ЦИФРА >  < БУКВА ИЛИ ЦИФРА 3 >  ::=  < БУКВА ИЛИ ЦИФРА >  < БУКВА >  ::= = a | b | c | [...] < ЦИФРА >  ::= = 0 | 1 | 2 | [...]  < ИМЕНА1 >  ::= = < ИМЕНА >  < ИМЕНА2 >  ::= = < ИМЕНА >  < НАЗНАЧЕНО >  ::= = < ИМЕНА >  < ИСПОЛЬЗУЕТСЯ >  ::= = < ИМЕНА >  < ИМЕНА >  ::= = < ИМЯ > | < ИМЯ >  < ИМЕНА >  < ПУСТО >  ::= = < TYPEMAP >  ::= = ( < ТИПИРОВАНО >  < ИМЯ > ) < TYPEMAP >  < TYPEMAP1 >  ::= = < TYPEMAP >  < TYPEMAP2 >  ::= = < TYPEMAP >  < TYPEMAP3 >  ::= = < TYPEMAP >

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

Новые гиперправила являются ε -правилами: они генерируют только пустую строку.

Примеры АЛГОЛа 68

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

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

а) программа: открытый символ, стандартная прелюдия, опция прелюдии библиотеки, конкретная программа, выход, опция библиотечной постлюдии, стандартная постлюдия, символ закрытия. б) стандартная прелюдия: последовательность декларативной прелюдии. в) прелюдия к библиотеке: последовательность прелюдии к объявлению. г) конкретная программа: опция последовательности меток, сильное ЗАКРЫТОЕ недействительное предложение. e) выход: перейти на символ, буква e, буква x, буква i, буква t, метка символ. f) библиотечная постлюдия: интерлюдия с заявлениями. g) стандартная постлюдия: сильная недействительная оговорка поезд

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

программа: сильная недействительная новая закрытая статья A) ВНЕШНИЙ :: стандартный; библиотечный; системный; частный. B) СТОП :: метка буква s буква t буква o буква p. а) текст программы: маркер начала СТИЛЯ, новые прелюдии СЛОЯ1, параллельный токен, новый ПАКЕТ задач LAYER1, Конечный токен STYLE. б) прелюдии NEST1: стандартная прелюдия NEST1 с DECS1, Прелюдия к библиотеке NEST1 с DECSETY2, Прелюдия к системе NEST1 с DECSETY3, где (NEST1) — это (новый ПУСТО новый DECS1 DECSETY2 DECSETY3). в) NEST1 EXTERNAL прелюдия с DECSETY1: сильная пустота серии NEST1 с DECSETY1, перейти на токен; где (DECSETY1) — (ПУСТО), ПУСТО. г) Задачи NEST1: список системных задач NEST1, а также токен, Список пакетов задач пользователя NEST1. e) Задача системы NEST1: сильная пустота блока NEST1. f) Задача пользователя NEST1: конкретная прелюдия NEST2 с DECS, NEST2 конкретная программа ПАКЕТ, перейти на токен, NEST2 в частности постлюдия, где (NEST2) — это (NEST1 новый DECS STOP). ж) Конкретная программа NEST2: NEST2 новый LABSETY3 присоединился к определению метки из LABSETY3, сильная пустота NEST2 новый LABSETY3 ПРИЛАГАЕМЫЙ пункт. h) NEST присоединился к определению метки LABSETY: где (LABSETY) - это (ПУСТО), ПУСТО; где (LABSETY) — это (LAB1 LABSETY1), Определение метки NEST для LAB1, NEST присоединился к определению метки $ LABSETY1. i) Конкретный постлюдь NEST2: прочная серия NEST2 с функцией STOP.

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

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

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

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

Реализации

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

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

Приложения вне ALGOL 68

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

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

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

Смотрите также

Ссылки

  1. ^ Кливленд, Дж. Крейг; Узгалис, Роберт К. (1977). Грамматики языков программирования . Elsevier. ISBN 978-0-444-00199-3.
  2. ^ ab van Wijngaarden, Adriaan (1972-04-04) [Преждевременное и предварительное издание 1965-10-22]. MR 76: Ортогональное проектирование и описание формального языка (PDF) (Технический отчет). Амстердам: CWI . Архивировано из оригинала (PDF) 2017-10-02.
  3. ^ ван Вейнгаарден, А.; и др. (ред.). "Пересмотренный отчет об алгоритмическом языке АЛГОЛ 68". Архивировано из оригинала 24 января 2002 г.
  4. ^ Костер, CHA (1996). «Создание Algol 68». В Bjørner, D; Broy, M.; Pottosin, IV (ред.). Перспективы системной информатики. Lecture Notes in Computer Science. Vol. 1181. Berlin: Springer. pp. 55–67. doi :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, получено 2023-06-14
  7. ^ Кнут, Дональд Э. (1990), «Генезис атрибутных грамматик» ( Plain TeX , gZiped ) , Труды Международной конференции по атрибутным грамматикам и их приложениям , Springer Verlag : 1–12.
  8. ^ Синцов, М. (1967). «Существование синтаксиса Ван Вейнгаардена для каждого рекурсивно перечислимого множества». Анналы научного общества Брюсселя . 81 : 115–118.
  9. ^ Аугусто, Л. М. (2023). «Двухуровневые грамматики: некоторые интересные свойства грамматик ван Вейнгаардена» (PDF) . Omega - Journal of Formal Languages ​​. 1 : 3–34.
  10. ^ Бэкус, Дж. В. и др. (1963). «Пересмотренный отчет об алгоритмическом языке АЛГОЛ 60». The Computer Journal . 5 (4): 349–367. doi : 10.1093/comjnl/5.4.349 .
  11. ^ "Синтаксис", Algol 68, FR : Univ Poitiers
  12. ↑ Фишер, Энтони (30 июля 2024 г.), «yo-yo», Software, Великобритания : York.
  13. ^ Грюн, Дик, Генератор двухуровневых предложений, NL : VU.
  14. ^ Альблас, Хенк; Меличар, Боривой (1991). Атрибутные грамматики, приложения и системы. Конспекты лекций по информатике. Том. 545. Спрингер. п. 371. ИСБН 978-3540545729.
  15. ^ Флауэрс, Рой, Описание W-грамматики для Ады (PDF) (магистерская диссертация), Технологический институт ВВС, Университет авиации

Дальнейшее чтение