Diskuze: Parser matematických výrazů

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 17:56

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

Neaktivní uživatelský účet

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 18:56

Kód jsem proletěl velmi rychle a toto je první věc, které jsem si všiml.
V metodách parseAddExp/parseMulExp 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

Neaktivní uživatelský účet

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 19:10

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

Neaktivní uživatelský účet

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 19:13

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

Neaktivní uživatelský účet

tomisoka

Tvůrce

tomisoka:12.12.2015 19:28

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

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 19:38

Když pro levý i pravý operand použiješ stejnou funkci (parseAddExp/MultExp), 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

Neaktivní uživatelský účet

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 20:26

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

Neaktivní uživatelský účet

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 20:40

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

Neaktivní uživatelský účet

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 20:41

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í
+2,50 Kč

Nahoru Odpovědět

12.12.2015 20:41

Neaktivní uživatelský účet

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 20:47

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

Neaktivní uživatelský účet

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 22:15

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

Nahoru Odpovědět

12.12.2015 22:15

Neaktivní uživatelský účet

Neaktivní uživatel

Člen

Neaktivní uživatel:12.12.2015 22:18

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

Neaktivní uživatelský účet