Как создать режим работы с regexparser?

Question

Я строй простого калькулятора с помощью Scala RegexParser, и я пытался создать правило для операций с использованием мощности ** следующим образом:

package com.pt.pedrorijo91.calc 

import scala.util.parsing.combinator.RegexParsers 
import scala.math.pow 

class Arith extends RegexParsers { 

    def number: Parser[Double] = """\d+(\.\d*)?""".r ^^ { _.toDouble } 

    def factor: Parser[Double] = number | "(" ~> expr <~ ")" | expr~"**"~expr ^^ { case x ~ "**" ~ y => pow(x,y)} 

    def term : Parser[Double] = factor ~ rep("*" ~ factor | "/" ~ factor) ^^ { 
    case number ~ list => list.foldLeft(number) { 
     case (x, "*" ~ y) => x * y 
     case (x, "/" ~ y) => x/y 
    } 
    } 

    def expr : Parser[Double] = term ~ rep("+" ~ term | "-" ~ term) ^^ { 
    case number ~ list => list.foldLeft(number) { 
     case (x, "+" ~ y) => x + y 
     case (x, "-" ~ y) => x - y 
    } 
    } 

} 

Я вставленное правило питания в factor методы, но если я пытаюсь для разбора "2 ** 3" он входит в бесконечный цикл.

Если вместо expr~"\*\*"~expr я использую number~"**"~number я получаю отказ от разбора со следующим сообщением:

строку соответствия регулярных выражений \d+(\.\d*)?' expected but *»найдено

Что мне не хватает?

Answer 1

кажется, что regexParser Scala строит рекурсивные партизаны спуска.

Проблема в том, что основная грамматика вашего анализатора не относится к классу синтаксического анализа грамматик (более формально она оставлена ​​рекурсивной).

производство factor -> epxr ** expr делает вашу грамматику левым рекурсивным (и двусмысленным).

Вы должны добавить еще один уровень (несимметричный символ), чтобы выразить, что ** имеет наивысший приоритет и использует только атомарные выражения в качестве своих аргументов для предотвращения неоднозначностей.

, что бы что-то вроде этого

atomicexpr -> number | (expr) 

factor -> atomicexpr (** atomicexpr)? 

отметить, что этот способ объединить succesive ** s вы будете вынуждены добавить скобки.