Разбор контекстно-зависимого языка

Я читаю ссылку на "Окончательный ANTLR" Теренса Парра, где он говорит:

Семантические предикаты являются мощным средством распознавания контекстно-зависимых языковых структур, позволяя информации времени выполнения управлять распознаванием

Но примеры в книге очень просты. Что мне нужно знать, так это: может ли ANTLR анализировать контекстно-зависимые правила, такие как:

xAy -> xBy

Если ANTLR не может разобрать эти правила, есть ли другой инструмент, который имеет дело с контекстно-зависимыми грамматиками?

Источник

1 ответ

Решение

ANTLR анализирует только грамматики, которые являются LL(*). Он не может проанализировать использование грамматик для полных контекстно-зависимых языков, таких как приведенный вами пример. Я думаю, что Парр имел в виду, что ANTLR может анализировать некоторые языки, которые требуют некоторых (левых) ограничений контекста.

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

Для нашего внешнего интерфейса на базе DMS на базе DMS Fortran существует контекстно-зависимая проверка, чтобы убедиться, что циклы DO правильно выстроены в линию. Рассматривать:

 DO  20, I= ...
   DO 10, J = ...
       ...
20  CONTINUE
10  CONTINUE

С точки зрения парсера лексический поток выглядит так:

DO  <number> , <variable> =  ...
    DO <number> , <variable> = ...
         ...
<number> CONTINUE
<number> CONTINUE

Как тогда парсер узнает, какой оператор DO идет с каким оператором CONTINUE? (сказать, что каждый DO соответствует своему ближайшему CONTINUE, не сработает, потому что FORTRAN может совместно использовать оператор CONTINUE с несколькими головками DO).

Мы используем семантический предикат "CheckMatchingNumbers" для сокращения для следующего правила:

block = 'DO' <number> rest_of_do_head newline 
         block_of_statements
         <number> 'CONTINUE' newline ; CheckMatchingNumbers

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

Фактические правила и семантические предикаты для обработки вложенности FORTRAN с общими продолжениями являются более сложными, чем это, но я думаю, что в этом суть.

То, что вы хотите, это полный контекстно-зависимый механизм синтаксического анализа. Я знаю, что их создали люди, но я не знаю ни одной полной реализации и не ожидаю, что они будут быстрыми.

Некоторое время я следовал грамматической системе MetaS Квинн Тейлор Джексон; это звучало как практическая попытка приблизиться.

Источник

Сравнительно легко написать контекстно-зависимый парсер в Prolog. Эта программа разбирает строку [a,is,less,than,b,and,b,is,less,than,c], превращая его в [a,<,b,<,c]:

:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :-
    rewrite_system([a,is,less,than,b,and,b,is,less,than,c],X),writeln('\nFinal output:'),writeln(X).

rewrite_rule([[A,<,B],and,[B,<,C]],[A,<,B,<,C]).
rewrite_rule([A,is,less,than,B],[A,<,B]).
rewrite_rule([[A,<,B],and,C,than,D],[[A,<,B],and,A,is,C,than,D]).
rewrite_rule([A,<,B],[[A,<,B]]).

rewritten(A) :- atom(A);bool(A).
bool(A) :- atom(A).
bool([A,<,B,<,C]) :- atom(A),atom(B),atom(C).
bool([A,and,B]) :- bool(A),bool(B).


% this predicate is from https://stackru.com/a/8312742/975097
replace(ToReplace, ToInsert, List, Result) :-
    once(append([Left, ToReplace, Right], List)),
    append([Left, ToInsert, Right], Result).

rewrite_system(Input,Output) :-
    rewritten(Input),Input=Output;
    rewrite_rule(A,B),
    replace(A,B,Input,Input1),
    writeln(Input1),
    rewrite_system(Input1,Output).

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

Источник
Другие вопросы по тегам