Неясности BNF - PullRequest
Новая
       27

Неясности BNF

0 голосов
/ 26 мая 2020

Книга "Конструирование компилятора" дает пример исходного определения Algol 60. Они содержат двусмысленность.

Найдите как минимум две разные структуры для 

IF a THEN b ELSE c=d

Есть часть определения 

unconditional Statement = basicStatement | forStatement | compoundStatement | ... .
ifStatement = "IF" BooleanExpression "THEN" unconditionalStatement.
conditionalStatement = ifStatement | ifStatement "ELSE" statement.

statement = unconditionalStatement | conditionalStatement.

, поэтому, поскольку: 

A "else" B, and A => "if" a "then" b

мы получаем: 

if a then b else B

и кажется, B это c=d

Где неясности? Как найти две разные конструкции?

1 Ответ

2 голосов
/ 26 мая 2020

IF a THEN b ELSE c=d не является утверждением. Это какое-то выражение; что это за зависит от типа b. (Это будет IF a THEN b ELSE c:=d.. Напомним, что в Algol := - это присваивание, = - сравнение на равенство, а == - синтаксическая ошибка.)

Если b - логическое значение, тогда это логическое условное выражение с альтернативами b и c=d; в этом случае c и d должны иметь тип arithmeti c, потому что грамматика не позволяет сравнивать логические значения с =.

Но если b - это arithmeti c, тогда это сравнение между условным выражением arithemti c IF a THEN b ELSE c и d (и, опять же, c и d должны иметь тип arithmeti c).

По крайней мере, это мое чтение грамматики. Это не совсем двусмысленно, но BNF недостаточно для разрешения синтаксического анализа, потому что язык не является контекстно-независимым. Для выбора правильного синтаксического анализа требуется предыдущее объявление b, что может быть достигнуто только с помощью контекстно-зависимой грамматики.

...