Diskuze: Parser matematických výrazů

C# .NET .NET (C# a Visual Basic) Parser matematických výrazů American English version English version

Avatar
Jakub Šárník:

Zdravím komunitu, dělám jednoduchý parser matematických výrazů produkující abstraktní syntaktický strom (jen int, závorky, základní operace a unární negace) a narazil jsem na problém:
Při zřetězení jedné binární operace se vyhodnotí špatně, např. 1 - 1 + 1 se vyhodnotí jako -1. Vím kde je chyba, ale netuším, jak ji opravit - chyba je tady:
1 - 1 + 1
(1) - (1 + 1) (rozdělení na LHS a RHS)
(1) - (2)
(-1)

Vycházím z následující gramatiky:

parse = exp EOF
exp = addExp
addExp = mulExp (('+' | '-') mulExp)*
mulExp = unaryExp (('*' | '/') unaryExp)*
unaryExp = '-' atom | atom
atom = Number | '(' exp ')'
Number = 0..9 //IN LEXER

Lexer i AST nody snad fungují, jen v parseru je probélm. Jeho kód je tady:

public class Parser
    {
        private TokenStream stream;

        public Parser(TokenStream input)
        {
            stream = input;
        }

        public Tree<int> Parse()
        {
            var tree = new Tree<int>(parseExp());
            stream.Expect(TokenType.EOF); //It must end with <EOF>
            return tree;
        }

        private IAstNode<int> parseExp()
        {
            return parseAddExp();
        }

        private IAstNode<int> parseAddExp()
        {
            var lhs = parseMulExp(); //Parse the LHS, it's always there

            if (stream.Match(TokenType.Add) || stream.Match(TokenType.Sub))
            {
                //RHS is present
                var tok = stream.Read(); //Eat '+' or '-'
                var rhs = parseAddExp(); //Parse the RHS

                if (tok.Matches(TokenType.Add))
                    return new AddNode(lhs, rhs);
                else if (tok.Matches(TokenType.Sub))
                    return new SubNode(lhs, rhs);
                throw new ParseError("Strange behaviour, this exception shouldn't be thrown");
            }
            else
            {
                return lhs;
            }
        }

        private IAstNode<int> parseMulExp()
        {
            var lhs = parseUnaryExp(); //Parse the LHS, it's always there

            if (stream.Match(TokenType.Mul) || stream.Match(TokenType.Div))
            {
                //RHS is present
                var tok = stream.Read(); //Eat '*' or '/'
                var rhs = parseMulExp(); //Parse the RHS

                if (tok.Matches(TokenType.Mul))
                    return new MulNode(lhs, rhs);
                else if (tok.Matches(TokenType.Div))
                        return new DivNode(lhs, rhs);
                throw new ParseError("Strange behaviour, this exception shouldn't be thrown");
            }
            else
            {
                return lhs;
            }
        }

        private IAstNode<int> parseUnaryExp()
        {
            if (stream.Match(TokenType.Sub))
            {
                //Unary with minus
                stream.Expect(TokenType.Sub); //Eat '-'
                return new NegNode(parseAtom());
            }
            else
            {
                //Unary without minus
                return parseAtom();
            }
        }

        private IAstNode<int> parseAtom()
        {
            if (stream.Match(TokenType.Number))
            {
                //This atom is a number
                int number = Int32.Parse(stream.Expect(TokenType.Number).Value); //Eat the number and save it
                return new NumberNode(number);
            }
            else
            {
                //This atom is a nested expression
                stream.Expect(TokenType.LPar); //Eat '('
                var inner = parseExp(); //Parse the inner expression
                stream.Expect(TokenType.RPar); //Eat ')'
                return inner;
            }
        }
    }

Některé pomocné funkce z TokenStream, což je wrapper nad List<Token>:

public Token Peek() => tokens[position];
public Token Read() => tokens[position++];
public bool Match(TokenType type) => Peek().Matches(type);

public bool Accept(TokenType type)
{
    if(Match(type))
    {
        Read();
        return true;
    }
    return false;
}

public Token Expect(TokenType type)
{
    if (Match(type))
        return Read();
    throw new ParseError(String.Format("Parse error: Expected '{0}', given '{1}'", type, Peek().Type));
}

Dost dlouho se už s tímhle otravuju a nevím si s tím rady. Proto doufám, že mě tady někdo pomůže a předem děkuji :-)

 
Odpovědět 12.12.2015 17:56
Avatar
Posix
Člen
Avatar
Odpovídá na Jakub Šárník
Posix:

Kód jsem proletěl velmi rychle a toto je první věc, které jsem si všiml.
V metodách parseAddExp/par­seMulExp nemáš lhs stejné jako rhs.

Tedy v parseAddExpr máš lhs = parseMulExp(), ale rhs = parseAddExpr();. Nemělo by být rhs taky parseMulExp();?

Podobně pro parseMulExp...

Jinak podle mě lhs a rhs je trochu něco jiného a nazval bych to spíš jako levý (první) a pravý (druhý) operand.

Nahoru Odpovědět 12.12.2015 18:56
Proč to dělat jednoduše, když to jde složitě.
Avatar
Odpovídá na Posix
Jakub Šárník:

U parseMulExp je ani stejné mít nemůžu, u parseAddExp jsem si toho teď všiml, ale nepamatuju si, proč jsem to tak napsal, takže to zkusím změnit a uvidím...

 
Nahoru Odpovědět 12.12.2015 19:10
Avatar
Odpovídá na Posix
Jakub Šárník:

Aha tak jak jsem zjistil, když to změním, začne to padat s ParseError

 
Nahoru Odpovědět 12.12.2015 19:13
Avatar
tomisoka
Redaktor
Avatar
Odpovídá na Jakub Šárník
tomisoka:

Na kód jsem se nedíval, ale ta chyba by co popisuješ na začátku by se dala vyřešit takto:
1 - 1 + 1 = 1 + (-1) + 1

 
Nahoru Odpovědět 12.12.2015 19:28
Avatar
Posix
Člen
Avatar
Odpovídá na Jakub Šárník
Posix:

Když pro levý i pravý operand použiješ stejnou funkci (parseAddExp/Mul­tExp), a místo ifu použiješ while, tak by to mělo fungovat. Aspoň v mém kódu to tak funguje. Tady je ukázka z mého parseru (není to hotové, ale zatím to dělá co má) http://www.itnetwork.cz/dev-lighter/656

Nahoru Odpovědět 12.12.2015 19:38
Proč to dělat jednoduše, když to jde složitě.
Avatar
Odpovídá na Posix
Jakub Šárník:

Je pravda, že ta gramatika nesedí úplně k tomu kódu, to jsem si teď všiml. Ale nedovedu ai to moc dobře představit jinak. Jak myslíš "stejnou funkci"? tomisoka no to je pravda, ale neřeší to můj problém :-D

 
Nahoru Odpovědět 12.12.2015 20:26
Avatar
Posix
Člen
Avatar
Odpovídá na Jakub Šárník
Posix:

Zkus tento vstup 1 - 1 + 1 + 1. Vyjde ti z toho (1 - (1 + (1 + 1))). Správně by to mělo být naopak (((1 - 1) + 1) + 1).

parseAddExp:

IAstNode<int> lhs = parseMulExp();
while (stream.Match(TokenType.Add) || stream.Match(TokenType.Sub))
{
    var tok = stream.Read();
    var rhs = parseMulExp();
    if (tok.Matches(TokenType.Add))
        lhs = new AddNode(node, rhs);
    else if (tok.Matches(TokenType.Sub))
        lhs = new SubNode(node, rhs);
    throw new ParseError("Strange behaviour, this exception shouldn't be thrown");
}
return lhs;
Nahoru Odpovědět 12.12.2015 20:40
Proč to dělat jednoduše, když to jde složitě.
Avatar
Posix
Člen
Avatar
Posix:

oprava: (nemuzu editovat)

IAstNode<int> lhs = parseMulExp();
while (stream.Match(TokenType.Add) || stream.Match(TokenType.Sub))
{
    var tok = stream.Read();
    var rhs = parseMulExp();
    if (tok.Matches(TokenType.Add))
        lhs = new AddNode(lhs, rhs);
    else if (tok.Matches(TokenType.Sub))
        lhs = new SubNode(lhs, rhs);
    throw new ParseError("Strange behaviour, this exception shouldn't be thrown");
}
return lhs;
Akceptované řešení
+20 Zkušeností
+1 bodů
Řešení problému
Nahoru Odpovědět 12.12.2015 20:41
Proč to dělat jednoduše, když to jde složitě.
Avatar
Odpovídá na Posix
Jakub Šárník:

Nevidím teda rozdíl mezi těma dvěma verzema :-D. No pravda je, že to hned vypadá líp s while a ne s rekurzí, jenže předtím mě to u volání mulExp v addExp rhs házelo chybu. Právěže vím kde mám chybu i jak by to mělo parsovat správně. Zkusím to hned jak budu na pc a uvidím... (u mulExp očekávam stejnou změnu)

 
Nahoru Odpovědět 12.12.2015 20:47
Avatar
Odpovídá na Posix
Jakub Šárník:

Tak po změně mě to padá na "Strange behaviour"...

 
Nahoru Odpovědět 12.12.2015 22:15
Avatar
Odpovídá na Jakub Šárník
Jakub Šárník:

Nemůžu editovat, ale to bylo jen přehlédnutí, tahle vyjímka tam nemá co dělat už :-D. Vypadá to, že to funguje :-)

 
Nahoru Odpovědět 12.12.2015 22:18
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 12 zpráv z 12.