Вопрос по грамматике
От: DSblizzard Россия  
Дата: 04.03.10 08:11
Оценка:
Бизон выдает 2 конфликта сдвиг/свертка на следующей грамматике:

%left ADD
%left MUL

%%

expr : expr bin_op expr
    | NAT
    ;

bin_op : ADD
    | MUL
    ;


Один человек, разбирающийся в подобных вещах, сказал, что грамматик, допускающих подобным образом выделение bin_op в отдельное правило без кофликтов, не существует. Мне не верится — ни GLR, ни Earley? Выглядит так просто. Хотелось бы услышать еще подтверждение — он прав?
Программировать сложно. Но не программировать еще сложнее.
Re: Вопрос по грамматике
От: Mr.Cat  
Дата: 04.03.10 08:17
Оценка:
Здравствуйте, DSblizzard, Вы писали:
DS>Бизон выдает 2 конфликта сдвиг/свертка на следующей грамматике:
DS>expr : expr bin_op expr
Это т.н. "левая рекурсия" (гуглябельно, но лучше почитать в книжках, типа Ахо с Ульманом). В данном случае проще устранить вручную, чем мучить парсеры.
Re[2]: Вопрос по грамматике
От: DSblizzard Россия  
Дата: 04.03.10 09:15
Оценка:
Здравствуйте, Mr.Cat, Вы писали:

MC>Это т.н. "левая рекурсия"

Да нет, левая рекурсия тут ни при чем, проблема во второй паре правил.

MC>В данном случае проще устранить вручную, чем мучить парсеры.

Я могу записать этот код без конфликтов, но тогда теряется моя цель — вынести bin_op отдельно. В достаточно больших грамматиках такой факторинг был бы полезен.
Программировать сложно. Но не программировать еще сложнее.
Re[3]: Вопрос по грамматике
От: Mr.Cat  
Дата: 04.03.10 09:37
Оценка:
Здравствуйте, DSblizzard, Вы писали:
MC>>Это т.н. "левая рекурсия"
DS>Да нет, левая рекурсия тут ни при чем, проблема во второй паре правил.
Сорри, не знал про сие

DS>Я могу записать этот код без конфликтов, но тогда теряется моя цель — вынести bin_op отдельно. В достаточно больших грамматиках такой факторинг был бы полезен.

Может, бизон для разрешения неоднозначности, требует, чтобы в неоднозначных правилах не шло подряд 2 и более нетерминала (емнип, такая грамматика называется операторной)? Попробуй во втором правиле оставить только 1 оператор — все равно будет конфликт?
Re[4]: Вопрос по грамматике
От: DSblizzard Россия  
Дата: 04.03.10 09:54
Оценка:
Здравствуйте, Mr.Cat, Вы писали:


MC>Может, бизон

Бизон, в принципе, меня не слишком интересует — это более общий вопрос, по всем грамматикам и генераторам парсеров.

MC>Попробуй во втором правиле оставить только 1 оператор — все равно будет конфликт?

Да. Объяснение здесь, начинается со слов "A hint: following grammar does not work"
Программировать сложно. Но не программировать еще сложнее.
Re[5]: Вопрос по грамматике
От: Mr.Cat  
Дата: 04.03.10 09:58
Оценка: 5 (1)
Здравствуйте, 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)).
Re[6]: Вопрос по грамматике
От: DSblizzard Россия  
Дата: 04.03.10 10:16
Оценка:
Здравствуйте, Mr.Cat, Вы писали:

MC>А нужно обязательно прям "expr = expr op expr"?

Да.
Программировать сложно. Но не программировать еще сложнее.
Re[7]: Вопрос по грамматике
От: Mr.Cat  
Дата: 04.03.10 10:17
Оценка:
Здравствуйте, DSblizzard, Вы писали:
MC>>А нужно обязательно прям "expr = expr op expr"?
DS>Да.
Даже не буду спрашивать, зачем. И сдаюсь.
Re: Вопрос по грамматике
От: mefrill Россия  
Дата: 04.03.10 11:46
Оценка: 15 (3) +1
Здравствуйте, DSblizzard, Вы писали:

DS>Один человек, разбирающийся в подобных вещах, сказал, что грамматик, допускающих подобным образом выделение bin_op в отдельное правило без кофликтов, не существует. Мне не верится — ни GLR, ни Earley? Выглядит так просто. Хотелось бы услышать еще подтверждение — он прав?


Тут дело не в LR-конфликте, а в неоднозначности самой грамматики. Вот, предположим, имеется такая строка

NAT ADD NAT MUL NAT


Для этой строки имеется два левых порождения (читай дерева):

expr ==> expr bin_op expr ==> NAT bin_op expr ==> NAT ADD expr ==> NAT ADD expr bin_op expr ==> NAT ADD NAT bin_op expr ==> NAT ADD NAT MUL expr ==> NAT ADD NAT MUL NAT

expr ==> expr bin_op expr ==> expr bin_op expr bin_op expr ==> NAT bin_op expr bin_op expr ==> NAT ADD expr bin_op expr ==> NAT ADD NAT bin_op expr ==> NAT ADD NAT MUL expr ==> NAT ADD NAT MUL NAT


Граматикая неоднозначная, значит заведомо LR(k)-анализатор не работает -- автомат не построишь, будут конфликты.

Относитльно Эрли: классический Эрли не парсит, а распознает, т.е. просто говорит о том, принадлежит строка языку, но не строит дерево попрождения данной строки. Эрли распознает все корректно. Но, чтобы Эрли парсил, надо классический алгоритм Эрли подкорректировать. я это когда-то сделал в моей диссертации, назвал такой алгоритм "адаптированный для построения деревьев вывода" алгоритм Эрли. Вот он построит оба дерева вместе. Относительно GLR не скажу т.к. не помню, по идее должен построить оба дерева, он вроде для правил без пустой правой частей всегда работает.

Вообще, это классическая проблема приоритета операций. Ее легче разрешить на синтаксическом уровне, т.е. ввести еще один нетерминал, который будет обозначать не просто "выражение", но "умножение", и заменить левый expr этим нетерминалом (если, конечно, сложение левоассоциативно). Можно разрешить синтаксический конфликт вручную выбрав только то дерево порождения, в котором NAT группируются сначала вокруг MUL.
Re[2]: Вопрос по грамматике
От: DSblizzard Россия  
Дата: 04.03.10 13:27
Оценка:
Здравствуйте, mefrill, Вы писали:

Но ведь я указал старшинство операторов и конфликт на вычисление результата не должен влиять. Значит, это виноват Бизон. Может быть, есть более умные генераторы?
Программировать сложно. Но не программировать еще сложнее.
Re: Вопрос по грамматике
От: VladD2 Российская Империя www.nemerle.org
Дата: 04.03.10 18:50
Оценка: 10 (1)
Здравствуйте, DSblizzard, Вы писали:

DS>Один человек, разбирающийся в подобных вещах, сказал, что грамматик, допускающих подобным образом выделение bin_op в отдельное правило без кофликтов, не существует. Мне не верится — ни GLR, ни Earley? Выглядит так просто. Хотелось бы услышать еще подтверждение — он прав?


Как я понимаю — это проблема скорее генераторов парсеров постреных по схеме yacc-а. При выделении чего-то в отдельное правило поведение парсера начинает отличаться от случае когда тоже самое записано по месту в одном парсере.

Что до других типов грамматик и построителей парсеров, то совершенно точно подобное возможно в PEG-нотации. Но там есть другие проблемы. Так нельзя задать приоритеты операторов (их прийдется выражать выделяя операторы в подправила) и недопустима левая рекурсия (в прочем прямая рекурсия разруливается многими построителями парсерами, например, Rats!-ом).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Вопрос по грамматике
От: mefrill Россия  
Дата: 05.03.10 11:53
Оценка:
Здравствуйте, DSblizzard, Вы писали:

DS>Но ведь я указал старшинство операторов и конфликт на вычисление результата не должен влиять. Значит, это виноват Бизон. Может быть, есть более умные генераторы?


Здесь дело не в операторах, а в нетерминале expr. Правила

expr : expr bin_op expr
     | NAT


представляют альтернативу. Можно подставить первое правило, а можно и второе. И каждая прдстановка в примере выше ведет к построению собственного дерева. Проблема в том, что в одних случаях тебе надо подставлять первое правило, а в других -- второе. В этом и неоднозначность, ее приоритетом операций так как ты хочешь не разрешить. В традиционой грамматике для разрешения неоднозначности цепляются за bin_op, т.е. за конкретный оператор (если спарва MUL, то всегда подставляем NAT), а ты эту возможность убрал.
Re[7]: Вопрос по грамматике
От: Буравчик Россия  
Дата: 05.03.10 20:28
Оценка:
Здравствуйте, DSblizzard, Вы писали:

DS>Здравствуйте, Mr.Cat, Вы писали:


MC>>А нужно обязательно прям "expr = expr op expr"?

DS>Да.

А в чем существенное отличие-то?

Вот этого:
expr : expr bin_op expr
    | NAT
    ;


от:
expr = expr2 bin_op expr2
expr2 = NAT | expr
... << RSDN@Home 1.2.0 alpha 4 rev. 1302>>
Best regards, Буравчик
Re[8]: Вопрос по грамматике
От: DSblizzard Россия  
Дата: 05.03.10 22:10
Оценка:
Здравствуйте, Буравчик, Вы писали:

Б>А в чем существенное отличие-то?


Б>Вот этого:

Б>
Б>expr : expr bin_op expr
Б>    | NAT
Б>    ;
Б>


Б>от:

Б>
Б>expr = expr2 bin_op expr2
Б>expr2 = NAT | expr
Б>


1) В вашем примере expr не может быть равен NAT.

2) Насколько я понял, в примере, который привел Mr. Cat, такая рекурсия не позволена. Вы думаете, что это не так?
Программировать сложно. Но не программировать еще сложнее.
Re[9]: Вопрос по грамматике
От: Буравчик Россия  
Дата: 05.03.10 22:37
Оценка:
Здравствуйте, 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



Пример:

*Main> parseTest parser "5*5+5"
BinOp ADD (BinOp MUL NAT NAT) NAT

*Main> parseTest parser "5"
NAT

... << RSDN@Home 1.2.0 alpha 4 rev. 1302>>
Best regards, Буравчик
Re[4]: Вопрос по грамматике
От: DSblizzard Россия  
Дата: 06.03.10 12:12
Оценка:
Здравствуйте, mefrill, Вы писали:

M>В традиционой грамматике для разрешения неоднозначности цепляются за bin_op, т.е. за конкретный оператор (если спарва MUL, то всегда подставляем NAT), а ты эту возможность убрал.


Рассмотрим восходящий анализатор для выражения 1 + 2 * 3 в тот момент, когда он прошел три терминала: expr bin_op expr | * 3. По-моему, вполне можно добавить поддержку запоминания приоритета левого оператора после его свертки. Никак не могу понять, в чем принципиальная трудность.
Программировать сложно. Но не программировать еще сложнее.
Re[10]: Вопрос по грамматике
От: DSblizzard Россия  
Дата: 06.03.10 12:13
Оценка:
Трудновато вчитаться в незнакомый синтаксис.
Что-то непонятно, почему Parsec не может решить задачу прямо, не используя expr2.
И еще, у вас учтен приоритет? Выражение 1 + 2 * 3 разберется правильно?
Программировать сложно. Но не программировать еще сложнее.
Re[11]: Вопрос по грамматике
От: Буравчик Россия  
Дата: 06.03.10 17:25
Оценка: 10 (1)
Здравствуйте, 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 поставленная Вами задача в исходном выражении решается достаточно просто.
... << RSDN@Home 1.2.0 alpha 4 rev. 1302>>
Best regards, Буравчик
Re[5]: Вопрос по грамматике
От: mefrill Россия  
Дата: 06.03.10 18:47
Оценка:
Здравствуйте, DSblizzard, Вы писали:

DS>Рассмотрим восходящий анализатор для выражения 1 + 2 * 3 в тот момент, когда он прошел три терминала: expr bin_op expr | * 3. По-моему, вполне можно добавить поддержку запоминания приоритета левого оператора после его свертки. Никак не могу понять, в чем принципиальная трудность.


Принципиальной трудности в реализации таких вещей нет, вопрос только: зачем это нужно? Неоднозначности такого рода могут быть разрешены переработкой грамматики. Странно было бы ожидать реализации такой специфической функциональности ради непонятного желания иметь грамматику именно подобного рода.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.