Бизон выдает 2 конфликта сдвиг/свертка на следующей грамматике:
%left ADD
%left MUL
%%
expr : expr bin_op expr
| NAT
;
bin_op : ADD
| MUL
;
Один человек, разбирающийся в подобных вещах, сказал, что грамматик, допускающих подобным образом выделение bin_op в отдельное правило без кофликтов, не существует. Мне не верится — ни GLR, ни Earley? Выглядит так просто. Хотелось бы услышать еще подтверждение — он прав?
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали: DS>Бизон выдает 2 конфликта сдвиг/свертка на следующей грамматике: DS>expr : expr bin_op expr
Это т.н. "левая рекурсия" (гуглябельно, но лучше почитать в книжках, типа Ахо с Ульманом). В данном случае проще устранить вручную, чем мучить парсеры.
Здравствуйте, Mr.Cat, Вы писали:
MC>Это т.н. "левая рекурсия"
Да нет, левая рекурсия тут ни при чем, проблема во второй паре правил.
MC>В данном случае проще устранить вручную, чем мучить парсеры.
Я могу записать этот код без конфликтов, но тогда теряется моя цель — вынести bin_op отдельно. В достаточно больших грамматиках такой факторинг был бы полезен.
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали: MC>>Это т.н. "левая рекурсия" DS>Да нет, левая рекурсия тут ни при чем, проблема во второй паре правил.
Сорри, не знал про сие
DS>Я могу записать этот код без конфликтов, но тогда теряется моя цель — вынести bin_op отдельно. В достаточно больших грамматиках такой факторинг был бы полезен.
Может, бизон для разрешения неоднозначности, требует, чтобы в неоднозначных правилах не шло подряд 2 и более нетерминала (емнип, такая грамматика называется операторной)? Попробуй во втором правиле оставить только 1 оператор — все равно будет конфликт?
MC>Может, бизон
Бизон, в принципе, меня не слишком интересует — это более общий вопрос, по всем грамматикам и генераторам парсеров.
MC>Попробуй во втором правиле оставить только 1 оператор — все равно будет конфликт?
Да. Объяснение здесь, начинается со слов "A hint: following grammar does not work"
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали: MC>>Попробуй во втором правиле оставить только 1 оператор — все равно будет конфликт? DS>Да. Объяснение здесь, начинается со слов "A hint: following grammar does not work"
А нужно обязательно прям "expr = expr op expr"? Например, парсек умеет вот так: http://osdir.com/ml/haskell-cafe@haskell.org/2009-07/msg00373.html
("expr = expr2 op expr2, expr2 = whatever | (expr)).
Здравствуйте, DSblizzard, Вы писали:
DS>Один человек, разбирающийся в подобных вещах, сказал, что грамматик, допускающих подобным образом выделение bin_op в отдельное правило без кофликтов, не существует. Мне не верится — ни GLR, ни Earley? Выглядит так просто. Хотелось бы услышать еще подтверждение — он прав?
Тут дело не в LR-конфликте, а в неоднозначности самой грамматики. Вот, предположим, имеется такая строка
NAT ADD NAT MUL NAT
Для этой строки имеется два левых порождения (читай дерева):
Граматикая неоднозначная, значит заведомо LR(k)-анализатор не работает -- автомат не построишь, будут конфликты.
Относитльно Эрли: классический Эрли не парсит, а распознает, т.е. просто говорит о том, принадлежит строка языку, но не строит дерево попрождения данной строки. Эрли распознает все корректно. Но, чтобы Эрли парсил, надо классический алгоритм Эрли подкорректировать. я это когда-то сделал в моей диссертации, назвал такой алгоритм "адаптированный для построения деревьев вывода" алгоритм Эрли. Вот он построит оба дерева вместе. Относительно GLR не скажу т.к. не помню, по идее должен построить оба дерева, он вроде для правил без пустой правой частей всегда работает.
Вообще, это классическая проблема приоритета операций. Ее легче разрешить на синтаксическом уровне, т.е. ввести еще один нетерминал, который будет обозначать не просто "выражение", но "умножение", и заменить левый expr этим нетерминалом (если, конечно, сложение левоассоциативно). Можно разрешить синтаксический конфликт вручную выбрав только то дерево порождения, в котором NAT группируются сначала вокруг MUL.
Но ведь я указал старшинство операторов и конфликт на вычисление результата не должен влиять. Значит, это виноват Бизон. Может быть, есть более умные генераторы?
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали:
DS>Один человек, разбирающийся в подобных вещах, сказал, что грамматик, допускающих подобным образом выделение bin_op в отдельное правило без кофликтов, не существует. Мне не верится — ни GLR, ни Earley? Выглядит так просто. Хотелось бы услышать еще подтверждение — он прав?
Как я понимаю — это проблема скорее генераторов парсеров постреных по схеме yacc-а. При выделении чего-то в отдельное правило поведение парсера начинает отличаться от случае когда тоже самое записано по месту в одном парсере.
Что до других типов грамматик и построителей парсеров, то совершенно точно подобное возможно в PEG-нотации. Но там есть другие проблемы. Так нельзя задать приоритеты операторов (их прийдется выражать выделяя операторы в подправила) и недопустима левая рекурсия (в прочем прямая рекурсия разруливается многими построителями парсерами, например, Rats!-ом).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, DSblizzard, Вы писали:
DS>Но ведь я указал старшинство операторов и конфликт на вычисление результата не должен влиять. Значит, это виноват Бизон. Может быть, есть более умные генераторы?
Здесь дело не в операторах, а в нетерминале expr. Правила
expr : expr bin_op expr
| NAT
представляют альтернативу. Можно подставить первое правило, а можно и второе. И каждая прдстановка в примере выше ведет к построению собственного дерева. Проблема в том, что в одних случаях тебе надо подставлять первое правило, а в других -- второе. В этом и неоднозначность, ее приоритетом операций так как ты хочешь не разрешить. В традиционой грамматике для разрешения неоднозначности цепляются за bin_op, т.е. за конкретный оператор (если спарва MUL, то всегда подставляем NAT), а ты эту возможность убрал.
Здравствуйте, DSblizzard, Вы писали:
DS>1) В вашем примере expr не может быть равен NAT.
DS>2) Насколько я понял, в примере, который привел Mr. Cat, такая рекурсия не позволена. Вы думаете, что это не так?
Речь была конкретно о parsec. Он разруливает левую рекурсию с помощью "chain":
nat `chainl1` op = nat op nat op nat ...
Это работает тажке и для одного nat.
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Token
import Text.ParserCombinators.Parsec.Language
data Expr = BinOp Op Expr Expr | NAT deriving Show
data Op = MUL | ADD deriving Show
nat = natural haskell >> return NAT
add = char '+' >> return ADD
mul = char '*' >> return MUL
-- expr = expr bin_op expr | NAT
expr = expr2 `chainl1` binop
expr2 = nat <|> expr
binop = do
op <- (add <|> mul)
return $ BinOp op
parser = do
e <- expr
eof
return e
Здравствуйте, mefrill, Вы писали:
M>В традиционой грамматике для разрешения неоднозначности цепляются за bin_op, т.е. за конкретный оператор (если спарва MUL, то всегда подставляем NAT), а ты эту возможность убрал.
Рассмотрим восходящий анализатор для выражения 1 + 2 * 3 в тот момент, когда он прошел три терминала: expr bin_op expr | * 3. По-моему, вполне можно добавить поддержку запоминания приоритета левого оператора после его свертки. Никак не могу понять, в чем принципиальная трудность.
Программировать сложно. Но не программировать еще сложнее.
Трудновато вчитаться в незнакомый синтаксис.
Что-то непонятно, почему Parsec не может решить задачу прямо, не используя expr2.
И еще, у вас учтен приоритет? Выражение 1 + 2 * 3 разберется правильно?
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали:
DS>Что-то непонятно, почему Parsec не может решить задачу прямо, не используя expr2.
Ну прямо тоже можно.
expr = (nat <|> expr) `chainl1` binop -- это равносильно expr bin_op expr, где expr = nat | expr
Переменная expr2 была введена, чтобы приблизиться к указанному Вами идеалу (expr bin_op expr).
Однако самый прямой вариант (expr = exrp >> op >> expr) работать не будет.
Т.к. описание грамматики Parsec фактически является программой на Haskell, то эта программа зациклится.
При вызове expr вызывает expr, который вызывает expr и т.д.
Для разруливания данных ситуаций Parsec имеет несколько комбинаторов "chainXX".
По своей сути они решают вопрос с рекурсией, но описание грамматики выглядит немного иначе.
Чтобы описать выражение (Elem op Elem op Elem ..., где op — левоассоциативна) указывается (Elem `chainl1` op).
DS>Трудновато вчитаться в незнакомый синтаксис.
Синтаксис не очень сложен. И фактически является синтаксисом Haskell для монад.
-- Правило описывает последовательность термов
term = do
term1
term2
-- Это то же самое
term = term1 >> term2
-- И это тоже
term = do { term1; term2 }
-- Правило описывает варианты
term = term1 <|> term2 <|> term3
-- return позволяет вернуть результат после парсинга
-- выражение вида (e <- parser) обозначает распарсить вход и присвоить результат переменной е
nat = do
n <- natural haskell
return n
-- парсится выражение вида "5+8" и вычисляется эта сумма
addExpr = do
n1 <- nat
char '+'
n2 <- nat
return (n1+n2)
-- Пример
-- *Main> parseTest addExpr "5+6"
-- 11
Вот вроде и все, что использовалось в примере.
DS>И еще, у вас учтен приоритет? Выражение 1 + 2 * 3 разберется правильно?
В данном варианте приоритет не учитывался, но Парсек имеет гибкий способ парсинга выражений:
— Описываются таблица допустимых операций (приоритет, ассоциативность и пр.)
— Описывается парсер для елементов выражения.
— С помощью buildExpressionParser формируется парсер который обрабатывает выражение вида (term op term op term ...), где op — описанные операции.
Но выглядит это как-то так:
expr = buildExpressionParser table term
term = parens expr <|> natural
table = [ [prefix "-" negate, prefix "+" id ]
, [postfix "++" (+1)]
, [binary "*" (*) AssocLeft, binary "/" (div) AssocLeft ]
, [binary "+" (+) AssocLeft, binary "-" (-) AssocLeft ]
]
binary name fun assoc = Infix (do{ reservedOp name; return fun }) assoc
prefix name fun = Prefix (do{ reservedOp name; return fun })
postfix name fun = Postfix (do{ reservedOp name; return fun })
Итого:
Parsec не умеет обрабатывать левую рекрсию в лоб (expr = expr op expr), т.е. Вашего оппонента в данном случае убедить не удастся
Однако при использовании Parsec можно работать с рекурсией, особым образом указав на ее наличие.
А при использовании buildExpressionParser поставленная Вами задача в исходном выражении решается достаточно просто.
Здравствуйте, DSblizzard, Вы писали:
DS>Рассмотрим восходящий анализатор для выражения 1 + 2 * 3 в тот момент, когда он прошел три терминала: expr bin_op expr | * 3. По-моему, вполне можно добавить поддержку запоминания приоритета левого оператора после его свертки. Никак не могу понять, в чем принципиальная трудность.
Принципиальной трудности в реализации таких вещей нет, вопрос только: зачем это нужно? Неоднозначности такого рода могут быть разрешены переработкой грамматики. Странно было бы ожидать реализации такой специфической функциональности ради непонятного желания иметь грамматику именно подобного рода.