2004-gre-cs-practice-book.pdf/Q35 — различия между версиями

Текущая версия на 21:25, 14 декабря 2024

Вопрос: Q35-4c9f66

Рассмотрим следующую грамматику

Какое из следующих утверждений является верным?

1. Грамматика неоднозначна
2. Грамматика подходит для нисходящего анализа
3. Грамматика подходит для восходящего анализа

Ответы

• Только 1
• Только 2
• Только 3
• Правильный ответ: 2 и 3
• 1, 2, 3

Объяснение

Исходники — вопрос 35 на 27 странице книги «2004-gre-cs-practice-book.pdf»

• Ну первое невозможно — язык понятный и однозначный по выводу, терминал «x» окруженный парным количеством скобок.
• Для однозначной грамматики легко написать как нисходящий… (его удобно писать на любых, сколь угодно жалких языках)

def нисходящий_разбор(слово):
    длина = len(слово)
    индекс = 0  
 
    def S():
        nonlocal индекс
        if индекс < длина:
            символ = слово[индекс]
            if символ == 'x':
                индекс += 1  # S -> x
            elif символ == '(':
                # S -> (S)
                индекс += 1  # сьедаем '('
                S()  # Рекурсивно разбираем S сверху вниз
                if индекс < длина and слово[индекс] == ')':
                    индекс += 1  # сьедаем ')'
                else:
                    return False
            else:
                return False
        return True    
 
    рез = S()
    if not рез or индекс < длина:
        return False
    return True
 
assert(нисходящий_разбор("(x)"))
assert(нисходящий_разбор("((x))"))
assert(not нисходящий_разбор("((x)"))
assert(not нисходящий_разбор("(x))"))

… так и восходящий разбор (но тут лучше использовать какой-нибудь генератор LR-парсеров).