Однозначная грамматика для выражений с let и добавлением - PullRequest
Новая
       63

Однозначная грамматика для выражений с let и добавлением

0 голосов
/ 05 ноября 2018

Что такое однозначная грамматика, эквивалентная следующей неоднозначной грамматике для языка выражений с let и добавлением ?

E ⇒ пусть id = E в E

E ⇒ E + E

E ⇒ num

Неоднозначность должна быть решена так:

  • сложение является ассоциативным
  • сложение имеет более высокий приоритет, чем выражения let, когда оно появляется справа
  • сложение имеет более низкий приоритет, чем выражения let, когда оно появляется слева

Используя фигурные скобки, чтобы показать группировку подвыражений, следующее иллюстрирует, как выражения должны интерпретироваться:

num + num + num => { num + num } + num

let id = num in num + num => let id = num in { num + num }

num + let id = num in num => num + { let id = num in num }

1 Ответ

0 голосов
/ 05 ноября 2018

Рассмотрим выражение

E<sub>1</sub> + E<sub>2</sub>

E<sub>1</sub> не может иметь форму let ID = E<sub>3</sub>, потому что let ID = E<sub>3</sub> + E<sub>2</sub> должен быть проанализирован как let ID = (E<sub>3</sub> + E<sub>2</sub>). Это ограничение является рекурсивным: оно также не может иметь форму E<sub>4</sub> + let ID = E<sub>3</sub>.

E<sub>2</sub> может иметь форму let ID = E<sub>3</sub>, но не может иметь форму E<sub>3</sub> + E<sub>4</sub> (поскольку E<sub>1</sub> + E<sub>3</sub> + E<sub>4</sub> должен быть проанализирован как (E<sub>1</sub> + E<sub>3</sub>) + E<sub>4</sub>). Только E<sub>1</sub> может иметь форму E<sub>3</sub> + E<sub>4</sub>.

Прямое (но повторяющееся) преобразование этих ограничений в BNF: 

Expr      ⇒ Sum

Sum       ⇒ SumNoLet '+' Atom
          | Atom
SumNoLet  ⇒ SumNoLet '+' AtomNoLet
          | AtomNoLet

AtomNoLet ⇒ num
          | id
          | '(' Expr ')'
Atom      ⇒ AtomNoLet
          | 'let' id '=' Expr

Чтобы сделать шаблон более понятным, мы можем добавить оператор *: 

Expr      ⇒ Sum

Sum       ⇒ SumNoLet '+' Prod
          | Prod
SumNoLet  ⇒ SumNoLet '+' ProdNoLet
          | ProdNoLet

Prod      ⇒ ProdNoLet '*' Atom
          | Atom
ProdNoLet ⇒ ProdNoLet '*' AtomNoLet
          | AtomNoLet

AtomNoLet ⇒ num
          | id
          | '(' Expr ')'
Atom      ⇒ AtomNoLet
          | 'let' id '=' Expr

Это можно реализовать в bison (или других аналогичных генераторах синтаксического анализатора), используя объявления приоритетов. Но решение о приоритете труднее рассуждать, и его сложно ввести в более сложные грамматики.

...