search

aripiprazole / rinha-de-compiler

🥖 | Rinha de compiladores (ou interpretadores kkkk
913 stars 226 forks source link

AST foi gerada corretamente? #225

Open omurilo opened 9 months ago

omurilo commented 9 months ago

A título de informação eu fiz meu parser & lexer e tentei gerar a AST para esse exemplo e na hora de interpretar acabei pegando o erro, então resolvi gerar a AST com a ferramenta rinha e tentar interpretar.

Usando o seguinte código

// symbols.rinha
if (1 + 2 == 3 && 3 <= 2 || 2 == 1) {
   print("hello")
} else {
   print("wellcome to hell")
}

Temos a seguinte AST gerada pela rinha:

{"name":"symbols.rinha","expression":{"kind":"If","condition":{"kind":"Binary","lhs":{"kind":"Binary","lhs":{"kind":"Int","value":1,"location":{"start":4,"end":5,"filename":"symbols.rinha"}},"op":"Add","rhs":{"kind":"Int","value":2,"location":{"start":8,"end":9,"filename":"symbols.rinha"}},"location":{"start":4,"end":9,"filename":"symbols.rinha"}},"op":"Eq","rhs":{"kind":"Binary","lhs":{"kind":"Int","value":3,"location":{"start":13,"end":14,"filename":"symbols.rinha"}},"op":"And","rhs":{"kind":"Binary","lhs":{"kind":"Int","value":3,"location":{"start":18,"end":19,"filename":"symbols.rinha"}},"op":"Lte","rhs":{"kind":"Binary","lhs":{"kind":"Int","value":2,"location":{"start":23,"end":24,"filename":"symbols.rinha"}},"op":"Or","rhs":{"kind":"Binary","lhs":{"kind":"Int","value":2,"location":{"start":28,"end":29,"filename":"symbols.rinha"}},"op":"Eq","rhs":{"kind":"Int","value":1,"location":{"start":33,"end":34,"filename":"symbols.rinha"}},"location":{"start":28,"end":34,"filename":"symbols.rinha"}},"location":{"start":23,"end":34,"filename":"symbols.rinha"}},"location":{"start":18,"end":34,"filename":"symbols.rinha"}},"location":{"start":13,"end":34,"filename":"symbols.rinha"}},"location":{"start":4,"end":34,"filename":"symbols.rinha"}},"then":{"kind":"Print","value":{"kind":"Str","value":"hello","location":{"start":47,"end":54,"filename":"symbols.rinha"}},"location":{"start":41,"end":55,"filename":"symbols.rinha"}},"otherwise":{"kind":"Print","value":{"kind":"Str","value":"wellcome to hell","location":{"start":74,"end":92,"filename":"symbols.rinha"}},"location":{"start":68,"end":93,"filename":"symbols.rinha"}},"location":{"start":0,"end":95,"filename":"symbols.rinha"}},"location":{"start":0,"end":95,"filename":"symbols.rinha"}}

Temos também a AST gerada pelo meu parser:

{"expression":{"condition":{"kind":"Binary","lhs":{"kind":"Int","location":{"start":1,"end":6,"filename":"symbols.rinha"},"value":1},"location":{"start":1,"end":8,"filename":"symbols.rinha"},"op":"Add","rhs":{"kind":"Binary","lhs":{"kind":"Int","location":{"start":1,"end":10,"filename":"symbols.rinha"},"value":2},"location":{"start":1,"end":13,"filename":"symbols.rinha"},"op":"Eq","rhs":{"kind":"Binary","lhs":{"kind":"Int","location":{"start":1,"end":15,"filename":"symbols.rinha"},"value":3},"location":{"start":1,"end":18,"filename":"symbols.rinha"},"op":"And","rhs":{"kind":"Binary","lhs":{"kind":"Int","location":{"start":1,"end":20,"filename":"symbols.rinha"},"value":3},"location":{"start":1,"end":23,"filename":"symbols.rinha"},"op":"Lte","rhs":{"kind":"Binary","lhs":{"kind":"Int","location":{"start":1,"end":25,"filename":"symbols.rinha"},"value":2},"location":{"start":1,"end":28,"filename":"symbols.rinha"},"op":"Or","rhs":{"kind":"Binary","lhs":{"kind":"Int","location":{"start":1,"end":30,"filename":"symbols.rinha"},"value":2},"location":{"start":1,"end":33,"filename":"symbols.rinha"},"op":"Eq","rhs":{"kind":"Int","location":{"start":1,"end":35,"filename":"symbols.rinha"},"value":1}}}}}}},"kind":"If","location":{"start":1,"end":3,"filename":"symbols.rinha"},"otherwise":{"kind":"Print","value":{"kind":"Str","location":{"start":4,"end":29,"filename":"symbols.rinha"},"value":"wellcome to hell"}},"then":{"kind":"Print","value":{"kind":"Str","location":{"start":2,"end":18,"filename":"symbols.rinha"},"value":"hello"}}},"name":"symbols.rinha"}

Desconsiderando os meus erros ao gerar a AST, gostaria de saber se a árvore gerada pela rinha estaá correta e o problema em vez da arvore seria o interpretador, já que o mesmo código em js é válido, ou se a árvore gerada não está correta.

jeffque commented 9 months ago

Eu creio que esteja errado. Perceba que todo código de exemplo .rinha fornecido pela organização não há encadeamento de mais do que 2 valores em uma operação, nem que para isso usem let para valores intermediários

    let a = k == 0;
    let b = k == n;
    if (a || b)

Em tese o operador que deveria ficar com o nó mais próximo de condicional deveria ser Or, mas não há regras de precedência na gramática da rinha para garantir isso