Анализ контекстно-зависимого языка

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

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

Для нашего внешнего интерфейса Fortran на основе DMS есть контекстно-зависимый убедитесь, что контуры 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://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).

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