Jak analizować tego typu wyrażeń?

Question

Nie mam tła kompilatora, więc nie jestem pewien, czy jest to coś commmon w tym obszarze. Czy istnieją standardowe metody analizowania wyrażeń takich jak ten? (Say, zakładka wskazuje głębokość)

And 
    A + B = 1 
    C + D = 1 
    Or 
     P + Q = 1 
     K = 1 
    And 
     Q = 1 
     R = 2 

powinien być analizowany jako:

((A+B=1) AND (C+D=1) AND ((P+Q=1) OR (K=1)) AND ((Q=1) AND (R=2))) 

Nie jestem pewien, czy należy odwołać się do oceny opartej stosu? Obecnie próbuję jednego z nich i opublikuję działający kod, jeśli uda mi się go uruchomić.

Wszelkie sugestie na prosty sposób, aby to osiągnąć?

Answer 1

Zakładając, że pytasz o sposób analizowania wyrażeń zbudowanych z operatorów o różnych priorytetach i skojarzeniach - absolutnie.

Jedno skuteczne podejście nazywa się "pierwszeństwem operatorów od góry", a być może także "priorytetem operatorów" i "wznoszeniem pierwszeństwa". Oto kilka ciekawych źródeł wyjaśniające podejście w szczegółach:

• Pratt parsing (również original paper)

• Douglas Crockforda na take na nim

• Pythonist na take na nim

• się Java version

Naprawdę fajną rzeczą jest to, jak mało kodu to zajmuje.

Kluczowe pojęcia to:

• prefiks vs wrostkiem vs mixfix

• pierwszeństwo: jest 3 + 4 * 5 analizowany jako (3 + 4) * 5 lub 3 + (4 * 5)?

• asocjatywność: czy x - y - z jest analizowany jako x - (y - z) lub (x - y) - z?

Przypadkowo, właśnie uczą się tych rzeczy niedawno i skończyło się pisząc artykuł na moim blogu o podobnym podejściu do analizowania operatora, który można znaleźć here. W moim podejściu zajmuję się operatorami infiksów, prefixów, postfiksów i mixfixów (to jest ? :); priorytety i asocjacje są określone w tabelach; Używam stosu do śledzenia operatorów, których operandy nie zostały jeszcze znalezione. Następnie analizator składni tworzy drzewo składniowe, w którym każdy węzeł jest podwyrażeniem.