FINÁLNÍ VÝPRODEJ KREDITŮ na ITnetwork je tady. Využij poslední šanci a získej až 80 % extra kreditů ZDARMA na náš interaktivní e-learning. Zjisti více:
NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Neaktivní uživatel
Člen
Avatar
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
Avatar
Neaktivní uživatel
Člen
Avatar
Odpovídá na Neaktivní uživatel
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/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
Neaktivní uživatelský účet
Avatar
Neaktivní uživatel
Člen
Avatar
Odpovídá na Neaktivní uživatel
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
Avatar
Neaktivní uživatel
Člen
Avatar
Odpovídá na Neaktivní uživatel
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
Avatar
tomisoka
Tvůrce
Avatar
Odpovídá na Neaktivní uživatel
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
Avatar
Neaktivní uživatel
Člen
Avatar
Odpovídá na Neaktivní uživatel
Neaktivní uživatel:12.12.2015 19:38

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
Neaktivní uživatelský účet
Avatar
Neaktivní uživatel
Člen
Avatar
Odpovídá na Neaktivní uživatel
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
Avatar
Neaktivní uživatel
Člen
Avatar
Odpovídá na Neaktivní uživatel
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
Avatar
Neaktivní uživatel
Člen
Avatar
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č
Řešení problému
Nahoru Odpovědět
12.12.2015 20:41
Neaktivní uživatelský účet
Avatar
Neaktivní uživatel
Člen
Avatar
Odpovídá na Neaktivní uživatel
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
Avatar
Neaktivní uživatel
Člen
Avatar
Odpovídá na Neaktivní uživatel
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
Avatar
Neaktivní uživatel
Člen
Avatar
Odpovídá na Neaktivní uživatel
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
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.