Грамматика Ван Вейнгаардена
В информатике — грамматика Ван Вейнгаардена (также 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]
Примеры
[ редактировать ]Соглашение в английской грамматике
[ редактировать ]В английском языке существительные, местоимения и глаголы имеют такие атрибуты, как грамматическое число , род и лицо , которые должны согласовываться между подлежащим , основным глаголом и местоимениями, относящимися к подлежащему:
- Я умываюсь.
- Она моется сама.
- Мы моемся.
являются действительными предложениями; недействительными являются, например:
- *Я умываюсь.
- *Она моется.
- *Мыемся.
Здесь соглашение служит для того, чтобы подчеркнуть, что оба местоимения (например, я и я ) относятся к одному и тому же человеку.
Контекстно-свободная грамматика для генерации всех таких предложений:
<sentence> ::= <subject> <verb> <object>
<subject> ::= I | You | He | She | We | They
<verb> ::= wash | washes
<object> ::= myself | yourself | himself | herself | ourselves | yourselves | themselves
От <sentence>, мы можем сгенерировать все комбинации:
I wash myself I wash yourself I wash himself [...] They wash yourselves They wash themselves
W-грамматика для генерации только допустимых предложений:
<sentence <NUMBER> <GENDER> <PERSON>>
::= <subject <NUMBER> <GENDER> <PERSON>>
<verb <NUMBER> <PERSON>>
<object <NUMBER> <GENDER> <PERSON>>
<subject singular <GENDER> 1st> ::= I
<subject <NUMBER> <GENDER> 2nd> ::= You
<subject singular male 3rd> ::= He
<subject singular female 3rd> ::= She
<subject plural <GENDER> 1st> ::= We
<subject singular <GENDER> 3rd> ::= They
<verb singular 1st> ::= wash
<verb singular 2nd> ::= wash
<verb singular 3rd> ::= washes
<verb plural <PERSON>> ::= wash
<object singular <GENDER> 1st> ::= myself
<object singular <GENDER> 2nd> ::= yourself
<object singular male 3rd> ::= himself
<object singular female 3rd> ::= herself
<object plural <GENDER> 1st> ::= ourselves
<object plural <GENDER> 2nd> ::= yourselves
<object plural <GENDER> 3rd> ::= themselves
<NUMBER> ::== singular | plural
<GENDER> ::== male | female
<PERSON> ::== 1st | 2nd | 3rd
Стандартный неконтекстно-свободный язык.
[ редактировать ]Хорошо известен неконтекстно-свободный язык.
Двухуровневая грамматика этого языка — метаграмматика.
- Н ::= 1 | N1
- X ::= а | б
вместе с грамматической схемой
- Начало ::= ⟨а Н ⟩ ⟨б Н ⟩ ⟨а Н ⟩
- ⟨Х N1 ⟩ ::= ⟨X Н ⟩ Х
- ⟨Х 1 ⟩ ::= Х
Вопросы. Если заменить N1 новой буквой, скажем, C, сохранится ли язык, порожденный грамматикой? Или N1 следует читать как строку из двух символов, то есть за N следует 1? Конец вопросов.
Требование допустимого использования переменных в ALGOL
[ редактировать ]Пересмотренный отчет об алгоритмическом языке Алгол 60 [10] определяет полный контекстно-свободный синтаксис языка.
Назначения определяются следующим образом (раздел 4.2.1):
<left part>
::= <variable> :=
| <procedure identifier> :=
<left part list>
::= <left part>
| <left part list> <left part>
<assignment statement>
::= <left part list> <arithmetic expression>
| <left part list> <Boolean expression>
А <variable> может быть (кроме всего прочего) <identifier>, что, в свою очередь, определяется как:
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
Примеры (раздел 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/C-v-q×S, все переменные должны быть числами; - в
V:=Q>Y^Z, все переменные должны иметь тип Boolean.
Вышеуказанные правила различают <arithmetic expression> и <Boolean expression>, но они не могут проверить, что одна и та же переменная всегда имеет один и тот же тип.
Это (неконтекстно-свободное) требование можно выразить в W-грамматике, аннотируя правила атрибутами, которые записывают для каждой используемой или присвоенной переменной ее имя и тип.
Эту запись затем можно перенести во все места грамматики, где необходимо сопоставить типы, и реализовать проверку типов.
Точно так же его можно использовать для проверки инициализации переменных перед использованием и т. д.
Можно задаться вопросом, как создавать такую структуру данных и манипулировать ею без явной поддержки в формализме структур данных и операций над ними. Это можно сделать, используя метаграмматику для определения строкового представления структуры данных и используя сопоставление с образцом для определения операций:
<left part with <TYPED> <NAME>>
::= <variable with <TYPED> <NAME>> :=
| <procedure identifier with <TYPED> <NAME>> :=
<left part list <TYPEMAP1>>
::= <left part with <TYPED> <NAME>>
<where <TYPEMAP1> is <TYPED> <NAME> added to sorted <EMPTY>>
| <left part list <TYPEMAP2>>
<left part with <TYPED> <NAME>>
<where <TYPEMAP1> is <TYPED> <NAME> added to sorted <TYPEMAP2>>
<assignment statement <ASSIGNED TO> <USED>>
::= <left part list <ASSIGNED TO>> <arithmetic expression <USED>>
| <left part list <ASSIGNED TO>> <Boolean expression <USED>>
<where <TYPED> <NAME> is <TYPED> <NAME> added to sorted <EMPTY>>
::=
<where <TYPEMAP1> is <TYPED1> <NAME1> added to sorted <TYPEMAP2>>
::= <where <TYPEMAP2> is <TYPED2> <NAME2> added to sorted <TYPEMAP3>>
<where <NAME1> is lexicographically before <NAME2>>
<where <TYPEMAP1> is <TYPED1> <NAME1> added to sorted <TYPEMAP2>>
::= <where <TYPEMAP2> is <TYPED2> <NAME2> added to sorted <TYPEMAP3>>
<where <NAME2> is lexicographically before <NAME1>>
<where <TYPEMAP3> is <TYPED1> <NAME1> added to sorted <TYPEMAP4>>
<where <EMPTY> is lexicographically before <NAME1>>
::= <where <NAME1> is <LETTER OR DIGIT> followed by <NAME2>>
<where <NAME1> is lexicographically before <NAME2>>
::= <where <NAME1> is <LETTER OR DIGIT> followed by <NAME3>>
<where <NAME2> is <LETTER OR DIGIT> followed by <NAME4>>
<where <NAME3> is lexicographically before <NAME4>>
<where <NAME1> is lexicographically before <NAME2>>
::= <where <NAME1> is <LETTER OR DIGIT 1> followed by <NAME3>>
<where <NAME2> is <LETTER OR DIGIT 2> followed by <NAME4>>
<where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 2>
<where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 2>
::= <where <LETTER OR DIGIT 1> precedes <LETTER OR DIGIT 2>
<where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 2>
::= <where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 3>
<where <LETTER OR DIGIT 3> precedes+ <LETTER OR DIGIT 2>
<where a precedes b> :==
<where b precedes c> :==
[...]
<TYPED> ::== real | integer | Boolean
<NAME> ::== <LETTER> | <NAME> <LETTER> | <NAME> <DIGIT>
<LETTER OR DIGIT> ::== <LETTER> | <DIGIT>
<LETTER OR DIGIT 1> ::= <LETTER OR DIGIT>
<LETTER OR DIGIT 2> ::= <LETTER OR DIGIT>
<LETTER OR DIGIT 3> ::= <LETTER OR DIGIT>
<LETTER> ::== a | b | c | [...]
<DIGIT> ::== 0 | 1 | 2 | [...]
<NAMES1> ::== <NAMES>
<NAMES2> ::== <NAMES>
<ASSIGNED TO> ::== <NAMES>
<USED> ::== <NAMES>
<NAMES> ::== <NAME> | <NAME> <NAMES>
<EMPTY> ::==
<TYPEMAP> ::== (<TYPED> <NAME>) <TYPEMAP>
<TYPEMAP1> ::== <TYPEMAP>
<TYPEMAP2> ::== <TYPEMAP>
<TYPEMAP3> ::== <TYPEMAP>
По сравнению с исходной грамматикой были добавлены три новых элемента:
- атрибуты нетерминалов в том, что сейчас называется гиперправилами;
- метаправила для указания допустимых значений атрибутов;
- новые гиперправила для указания операций над значениями атрибутов.
Новые гиперправила являются ε -правилами: они генерируют только пустую строку.
Алгол 68 примеров
[ редактировать ]В отчетах ALGOL 68 используются немного другие обозначения без <угловых скобок>.
АЛГОЛ 68, как указано в §2.1 итогового отчета 1968 г.
[ редактировать ]a) program : open symbol, standard prelude,
library prelude option, particular program, exit,
library postlude option, standard postlude, close symbol.
b) standard prelude : declaration prelude sequence.
c) library prelude : declaration prelude sequence.
d) particular program :
label sequence option, strong CLOSED void clause.
e) exit : go on symbol, letter e letter x letter i letter t, label symbol.
f) library postlude : statement interlude.
g) standard postlude : strong void clause train
АЛГОЛ 68, как указано в пересмотренном отчете 1973 г. §2.2.1, §10.1.1.
[ редактировать ] program : strong void new closed clause
A) EXTERNAL :: standard ; library ; system ; particular.
B) STOP :: label letter s letter t letter o letter p.
a) program text : STYLE begin token, new LAYER1 preludes,
parallel token, new LAYER1 tasks PACK,
STYLE end token.
b) NEST1 preludes : NEST1 standard prelude with DECS1,
NEST1 library prelude with DECSETY2,
NEST1 system prelude with DECSETY3, where (NEST1) is
(new EMPTY new DECS1 DECSETY2 DECSETY3).
c) NEST1 EXTERNAL prelude with DECSETY1 :
strong void NEST1 series with DECSETY1, go on token ;
where (DECSETY1) is (EMPTY), EMPTY.
d) NEST1 tasks : NEST1 system task list, and also token,
NEST1 user task PACK list.
e) NEST1 system task : strong void NEST1 unit.
f) NEST1 user task : NEST2 particular prelude with DECS,
NEST2 particular program PACK, go on token,
NEST2 particular postlude,
where (NEST2) is (NEST1 new DECS STOP).
g) NEST2 particular program :
NEST2 new LABSETY3 joined label definition
of LABSETY3, strong void NEST2 new LABSETY3
ENCLOSED clause.
h) NEST joined label definition of LABSETY :
where (LABSETY) is (EMPTY), EMPTY ;
where (LABSETY) is (LAB1 LABSETY1),
NEST label definition of LAB1,
NEST joined label definition of$ LABSETY1.
i) NEST2 particular postlude :
strong void NEST2 series with STOP.
Простым примером возможностей W-грамматик является предложение
a) program text : STYLE begin token, new LAYER1 preludes,
parallel token, new LAYER1 tasks PACK,
STYLE end token.
Это позволяет использовать BEGIN ... END и { } в качестве разделителей блоков, исключая при этом BEGIN ... } и { ... END.
Можно сравнить грамматику в отчете с анализатором Yacc для подмножества АЛГОЛА 68 Марка ван Леувена. [11]
Реализации
[ редактировать ]Энтони Фишер написал йо-йо , [12] синтаксический анализатор большого класса W-грамматик с примерами грамматик для eva выражений , sal и Pascal ( фактический стандарт ISO 7185 для Pascal использует расширенную форму Бэкуса-Наура ).
Дик Грюн создал программу на языке C , которая генерировала все возможные варианты W-грамматики. [13]
Приложения вне АЛГОЛА 68
[ редактировать ]Упомянутые выше применения расширенных аффиксных грамматик (EAG) можно эффективно рассматривать как приложения W-грамматик, поскольку EAG очень близки к W-грамматикам. [14]
W-грамматики также были предложены для описания сложных действий человека в эргономике . [ нужна ссылка ]
также предоставлено описание W-грамматики Для Ada . [15]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Кливленд, Дж. Крейг; Узгалис, Роберт К. (1977). Грамматики языков программирования . Эльзевир. ISBN 978-0-444-00199-3 .
- ^ Jump up to: а б ван Вейнгаарден, Адриан (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 года.