Что такое неоднозначная контекстно-свободная грамматика?

Question

Я не очень хорошо понимаю концепцию неоднозначности в контекстно-свободных грамматиках. Если бы кто-нибудь мог мне помочь и объяснить концепцию или предоставить хороший ресурс, я был бы очень признателен.

Answer 1

T * U;

Это объявление указателя или умножение? Вы не можете сказать, пока не знаете, что T а также U на самом деле

Таким образом, синтаксис выражения зависит от семантики (значения) выражения. Это не зависит от контекста - на языке без контекста это может быть только одно, а не два. (Вот почему они не позволили таким выражениям быть допустимыми утверждениями в D.)

Другой пример:

T<U> V;

Это использование шаблона или это операция больше или меньше? (Вот почему они изменили синтаксис на T!(U) V в D - круглые скобки имеют только одно использование, тогда как каретки имеют другое использование.)

Answer 2

Как бы вы проанализировали это:

if condition_1 then if condition_2 then action_1 else action_2

К какому "если" принадлежит "еще"?

В Python это:

if condition_1:
    if condition_2:
        action_1
    else:
        action_2

а также:

if condition_1:
    if condition_2:
        action_1
else:
    action_2

Answer 3

Рассмотрим входную строку, распознаваемую по контекстно-свободной грамматике. Строка получается неоднозначно, если она имеет два или более различных крайних левых вывода или разбирает деревья по вашему желанию. Грамматика неоднозначна, если она генерирует строки неоднозначно. Например, грамматика S -> E + E | E * E - неоднозначная грамматика, поскольку она выводит строку x + x * x неоднозначно, иными словами, существует более одного дерева разбора для представления выражения (на самом деле их два). Грамматику можно сделать не двусмысленной, изменив грамматику на:

E -> E + T | T

T -> T * F | F

F -> (E) | Икс

Реорганизованная грамматика всегда будет выводить строку однозначно, т. Е. Вывод всегда будет производить одно и то же дерево разбора.