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

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

11 голосов
/ 26 февраля 2011

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

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

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

xAy -> xBy

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

Ответы [ 2 ]

10 голосов
/ 27 февраля 2011

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

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

Для нашего основанного на DMS фронта Fortran на основе DMSend , есть контекстно-зависимая проверка, чтобы убедиться, что циклы 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 грамматическая система Куинна Тейлора Джексона какое-то время;это звучало как практическая попытка приблизиться.

0 голосов
/ 17 марта 2019

Сравнительно легко написать контекстно-зависимый парсер в Пролог .Эта программа анализирует строку [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://stackoverflow.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).

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

...