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

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) | х

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