Действительно ли это - неоднозначная грамматика? Как я должен разрешить его?
Для снабжения предисловием этого мое знание этого вида материала является маленьким.
Так или иначе я разрабатывал контекстно-свободную грамматику для описания структуры алгебраических выражений, таким образом, я могу самостоятельно учиться, как CYK парсинг алгоритма работает. Я понимаю, как такая структура может работать только с инфиксными алгебраическими выражениями, но я не могу понять, как разработать грамматику, которая может обработать и унарные и двоичные определения "-" оператор.
Для ссылки вот грамматика, которую я записал (где S является начальным символом) в CNF:
S-> x
A-> O S
S-> L B
B-> S R
S-> K S
O-> +
O-> -
O-> *
O-> /
O-> ^
K-> -
L-> (
R->)
Проблема состоит в том что, как CYK парсинг алгоритма может знать заранее, решить ли между S-> K S и-> O S, когда он встречается "-" оператор? Действительно ли такая грамматика больше контекстно-свободна? И самое главное, так как языки программирования могут обработать языки и с двоичным и с унарным знаком "минус", как я должен обоснованно проанализировать это?
3 ответа
Это похоже на проблему, связанную с конечными автоматами, и я не помню всего из моей курсовой работы, но я написал синтаксический анализатор CYK в OCaml, поэтому я продолжу и сделаю попытку :)
Если вы пытаетесь разобрать выражение вроде 3- -4 , например, у вас будет ] S -> Правило KS потребляет -4 , а затем ваше правило A -> OS поглощает - -4 . В конечном итоге это будет работать до самого верхнего производственного правила S . Тем не менее, вы должны быть осторожны с грамматикой, которую вы используете, поскольку указанное вами производственное правило A не может быть достигнуто из S , и вы, вероятно, должны иметь S -> SOS какое-то правило.
Алгоритмы синтаксического анализа CYK работают через отслеживание с возвратом, а не через «знание заранее», о котором вы упомянули в своем вопросе. Ваш алгоритм CYK должен проанализировать -4 как правило S -> KS , а затем попытаться поглотить второе - с помощью S -> KS снова, потому что это производственное правило допускает сколь угодно длинную цепочку унарных - . Но как только ваш алгоритм понимает, что он застрял на промежуточном синтаксическом анализе 3 S , он понимает, что у него нет производственных символов, которые он может использовать для этого.Как только он поймет, что это больше не поддается синтаксическому анализу, он вернется и вместо этого попытается проанализировать - как правило S -> O S и продолжит свой веселый путь.
Это означает, что ваша грамматика остается контекстно-независимой, поскольку контекстно-зависимая грамматика означает, что у вас есть терминалы слева от производственных правил, так что вы хороши в этом отношении. HTH!
Грамматика неоднозначна, и синтаксический анализатор не может решить, какой регистр выбрать.
Вам, вероятно, следует использовать следующую грамматику:
S -> EXPR
EXPR -> (EXPR)
EXPR -> - EXPR
EXPR -> EXPR + EXPR
EXPR -> EXPR - EXPR
// etc...
Грамматики, основанные на алгебраических выражениях, довольно трудно однозначно определить. Вот несколько примеров проблем, которые необходимо решить:
a+b+c естественно создает два дерева разбора. Чтобы решить эту проблему, вам нужно разрешить неоднозначность ассоциативности +. Вы можете позволить стратегии разбора слева направо позаботиться об этом за вас, но будьте осторожны: экспоненция, вероятно, должна ассоциироваться справа налево.
a+b*c естественным образом создает два дерева разбора. Чтобы решить эту проблему, необходимо разобраться с приоритетом операторов.
неявное умножение (a+bc), если оно разрешено, создает всевозможные кошмары, в основном при токенизации.
унарное вычитание проблематично, как вы упомянули.
Если мы хотим решить эти проблемы, но при этом иметь быстро разбираемую грамматику, специализированную для алгебры, один из подходов заключается в том, чтобы иметь различные "уровни" EXPR, по одному для каждого уровня связывания, требуемого уровнями предшествования. Например,
TERM -> (S)
EXPO -> TERM ^ EXPO
PROD -> PROD * EXPO
PROD -> PROD / EXPO
PROD -> -PROD
SUM -> SUM + PROD
SUM -> SUM - PROD
S -> SUM
Это требует, чтобы вы также разрешили "продвижение" типов: SUM -> PROD, PROD -> EXP, EXP -> TERM, и т.д., чтобы все могло завершиться.
Надеюсь, это поможет!