Gramatyka: różnica między górą a dołem? (Przykład)

Question

to jest kontynuacją pytanie od Grammar: difference between a top down and bottom up?

I sprawę z tej kwestii, że:

• sam gramatyczne nie jest od góry do dołu lub od dołu do góry, parser jest
• istnieje gramatyki, które mogą być przetwarzane przez jedną, ale nie drugiej
• (dzięki Jerry Coffin

Więc w tym gramatyki (wszystkie pos sible formuł matematycznych):

E -> E T E 
    E -> (E) 
    E -> D 

    T -> + | - | * |/

    D -> 0 
    D -> L G 

    G -> G G  
    G -> 0 | L 

    L -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

Czy można to odczytać za pomocą parsetu od góry do dołu i od dołu w górę?

Czy możesz powiedzieć, że jest to gramatyka odgórna lub gramatyka oddolna (lub żadna)?

---

Pytam bo mam pytanie domowe z pytaniem:

"Write top-down i bottom-up gramatyki dla języka obejmującej wszystkich ..." (inna kwestia)

Nie jestem pewien, czy to może być poprawne, ponieważ wydaje się, że nie ma czegoś takiego jak gramatyka odgórna i oddolna. Czy ktokolwiek mógłby wyjaśnić?

Answer 1

Ta gramatyka jest głupia, ponieważ jednoczy leksykon i analizuje. Ale ok, to akademicki przykład.

Rzecz z dnem do góry i odgórnym jest to, że ma specjalne narożniki, które są trudne do wdrożenia z tobą normalnie 1 patrzeć w przyszłość. Prawdopodobnie powinieneś sprawdzić, czy ma jakieś problemy i zmienić gramatykę.

Aby zrozumieć ty gramatyki pisałem właściwego EBNF

expr: 
    expr op expr | 
    '(' expr ')' | 
    number; 

op: 
    '+' | 
    '-' | 
    '*' | 
    '/'; 

number: 
    '0' | 
    digit digits; 

digits: 
    '0' | 
    digit | 
    digits digits; 

digit: 
    '1' | 
    '2' | 
    '3' | 
    '4' | 
    '5' | 
    '6' | 
    '7' | 
    '8' | 
    '9'; 

ja szczególnie nie podoba regułę digits: digits digits. Nie jest jasne, gdzie zaczynają się pierwsze cyfry, a drugie kończy. Chciałbym wdrożyć zasadę jako

digits: 
    '0' | 
    digit | 
    digits digit; 

Innym problemem jest to sprzeczne z number: '0' | digit digits;digits: '0' i digits: digit;. W rzeczywistości jest to duplikowane. Chciałbym zmienić zasady (usuwanie cyfr):

number: 
    '0' | 
    digit | 
    digit zero_digits; 

zero_digits: 
    zero_digit | 
    zero_digits zero_digit; 

zero_digit: 
    '0' | 
    digit; 

To sprawia, gramatykę LR1 (lewa rekurencyjne jednym spojrzeniem naprzód) i kontekstu darmo. Oto, co zwykle daje się generatorowi parsera, na przykład żubra. A ponieważ bison jest od dołu, jest to poprawne dane wejściowe dla parsera do dna.

Dla podejścia odgórnego, przynajmniej dla rekursywnej przyzwoitej, lewa rekurencja to trochę problem. Możesz użyć wycofania, jeśli chcesz, ale dla tych potrzebujesz gramatyki RR1 (prawy rekursywny jeden spojrzeć w przyszłość).Aby to zrobić zamień rekursje:

zero_digits: 
    zero_digit | 
    zero_digit zero_digits; 

Nie jestem pewien, czy to odpowiada na pytanie. Myślę, że to pytanie jest źle sformułowane i wprowadzające w błąd; i piszę parsery dla życia ...