BNFC-синтаксический анализатор и скобка Mathematica, как синтаксис

Question

Я немного поиграл с Конвертером BNF и попытался перестроить части языка Mathematica. Мой BNF уже имел около 150 строк и работал нормально, пока я не заметил очень простую ошибку. Скобки [] в Mathematica используются для двух разных вещей

1. expr[arg] вызвать функцию
2. list[[spec]] для доступа к элементам выражения, например List

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

f[]
f[a]
f[a,b,c]
f[[a]]
f[[a,b]]

f[a,f[b]]
f[[a,f[x]]]

Прямой, но явно неправильный входной файл для BNF C может выглядеть так

entrypoints Expr ;

TSymbol.        Expr1 ::= Ident ;
FunctionCall.   Expr ::= Expr "[" [Sequence] "]" ;
Part.           Expr ::= Expr "[[" [Sequence] "]]" ;    
coercions Expr 1 ;

separator Sequence "," ;
SequenceExpr. Sequence ::= Expr ;

Этот BNF не работает для двух последних примеров первого кодового блока.

Проблема, кажется, находится в созданном Yylex файл лексера, который соответствует ] а также ]] по отдельности. Это неправильно, потому что, как видно из последних примеров, является ли это закрытием или нет ] или же ]] зависит от контекста. Так что либо вы должны создать стек фигурных скобок, чтобы обеспечить правильное соответствие, либо оставить это парсеру.

Может ли кто-нибудь просветить меня, возможно ли это реализовать с помощью BNF C?

(Кстати, другие советы будут с благодарностью приняты)

Answer 1

Ваша проблема - это символ "]]". Если лексер собирает это без памяти о своем прошлом, он может ошибаться. Так что просто не делай этого!

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

Я бы определил вашу грамматику следующим образом:

FunctionCall.   Expr ::= Expr "[" [Sequence] "]" ;
Part.           Expr ::= Expr "[" "[" [Sequence] "]" "]" ;   

с лексером, определяющим только один "[" "]" как токены.

Странный вариант:

FunctionCall.   Expr ::= Expr "[" [Sequence] "]" ;
Part.           Expr ::= Expr "[[" [Sequence] "]" "]" ; 

с помощью лексера, также обнаруживающего "[[" в качестве токена, поскольку он не может быть ошибочным.