Грамматики простого и слабого предшествования

@palamo · Регистрация: 28.09.2017

Студворк — интернет-сервис помощи студентам

По каждой КС-грамматике G можно построить таблицу
предшествования T (точнее говоря, T(G)). Строки и столбцы таблицы
однозначно поименованы основными и вспомогательными символами грамматики
и дополнительным символом #.
В клетки T(x,y) таблицы помещаются символы <,=,> по следующим
правилам (в которых u и v могут быть произвольными строками):
1) T(x,y) содержит <, если G содержит правило вида A->uxBv такое,
что существует непустой вывод строки, начинающейся с y, из символа B.
2) T(x,y) содержит >, если y - основной символ, и G содержит правило
вида A->uBZv такое, что существуют непустой вывод строки, кончающейся
на x, из символа B и (возможно, пустой) вывод строки, начинающейся
с y, из символа Z (когда упомянутый последним вывод пуст, Z совпадает
с y).
3) T(x,y) содержит =, если G содержит правило вида A->uxyv.
4) T(#,y) содержит <, если в G из аксиомы можно вывести
строку, начинающуюся с y.
5) T(x,#) содержит >, если в G из аксиомы можно вывести
строку, кончающуюся на x.

Если T(x,y) содержит <, > или =, будем употреблять также
обозначения x<y, x>y, x=y, соответственно (заметим, что одно-
временно может быть x<y, x>y и x=y).

G называется грамматикой простого предшествования, если
каждое из множеств T(x,y) содержит не более одного элемента.
G называется грамматикой слабого предшествования, если
1) каждое из множеств T(x,y) одновременно ссимволом > не может
содержать ни символа <, ни символа =, 2) если G содержит два
правила A->uXv и B->v, то не может быть ни X<B, ни X=B.

Следующая грамматика для арифметических выражений типа a+a*(a*a+a)
является обратимой грамматикой слабого (но не простого) предшествования.

E->E+T | T
T->T*F | F
F->(E) | a

Ниже приводится таблица предшествования для этой грамматики

| E T F a ( ) + * #
__|___________________________
E | = =
T | > > = >
F | > > > >
a | > > > >
) | > > > >
( |<= < < < <
+ | <= < < <
* | = < <
# | < < < < <

Алгоритм анализа.

Ниже будем считать, что G - обратимая (т.е. не содержит
разных правил с одинаковой правой частью) и приведенная
(т.е. не содержит выводов вида A->B->...->A, и удовлетворяет
некоторым другим простым условиям, которые обычно выполняются
для естественным образом построенных грамматик).

Пусть s - входная строка, дополненная в конце символом #,
и m - вспомогательная строка (стек), вначале равная #.
На каждом шаге работы имеется указатель на некоторый символ строки
s (в начале работы указывается первый символ s) и указатель
на последний символ стека m.

Алгоритм состоит из этапов переноса и свертки.
Пусть x - последний символ стека m, y - очередной символ во
входной строке s.
1) Если x<y или x=y, то y переносится в m, и указатель на
s переносится на следующий символ.
2) Если x>y, то в хвосте m производится свертка (т.е. замена
правой части некоторого правила на его левую часть), если это
возможно. Для грамматик простого предшествования такое правило
(если оно есть) определяется однозначно. Для грамматик слабого
предшествования это может быть не так: в этом случае надо
заменять самую длинную правую часть. Если такого правила нельзя
найти, то s нельзя вывести в G;
3) Если T(x,y) пусто, то s нельзя вывести в G (кроме случая
x=E,y=#, в этом случае надо выйти из цикла и проверить стек
на равенство с #E как ниже).

Если таким образом удается обработать всю строку s и в конце
работы m равен #E, где E - аксиома грамматики G, то делается
вывод, что s можно вывести в G, а в противном случае -
s не выводится в G.

Добавлено через 2 минуты
Всем здравствуйте! Ладно, я сразу признаюсь, что я чайник. У меня есть небольшие знания - однако же, их хватило на то, чтобы выполнить первые две лабораторные, да и то с помощью. Эту программу я просто-напросто не понимаю. Не прошу просто сделать ее за меня и прислать, что вы. Но я бы очень попросила хотя бы совет, как начать, а то я в ступоре. Спасибо.

@Unril · 26.05.2012, 04:26

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
inputString = "(((1+1)+1)+1)"
 
stack = ["$", "S"]
 
def peek(list):
    return list[len(list) - 1]
 
states = ["F", "(S+F)", "1"]
 
actions = {
    "(": {"S": 2, "F": 0},
    ")": {"S": 0, "F": 0},
    "1": {"S": 1, "F": 3},
    "+": {"S": 0, "F": 0},
    "$": {"S": 0, "F": 0},
    }
 
accepted = False
pos = 0
inputString += "$"
while len(stack):
    terminal = inputString[pos]
    print("Terminal: %s" % terminal)
    state = peek(stack)
    if state == terminal:
        pos += 1
        stack.pop()
        print("Match: " + terminal)
    else:
        try:
            actionNumber = actions[terminal][state]
        except KeyError as e:
            print("Unknown symbol: %s!" % e)
            break
        if actionNumber:
            action = states[actionNumber - 1]
            oldState = stack.pop()
            stack += reversed(action)
            print("Action: %s -> %s" % (oldState, action))
        else:
            print("Error!")
            break
else:
    print("Done!")

LL-анализатор, LL parser, Пишем LR(0)-анализатор. Это не совсем соответствует заданию, но суть та же.

accept · 26.05.2012, 06:59

определение формальной грамматики

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@palamo 0 / 0 / 0 Регистрация: 28.09.2017 Сообщений: 9

	Грамматики простого и слабого предшествования 17.05.2012, 11:42. Показов 5573. Ответов 2 Метки грамматика (Все метки) По каждой КС-грамматике G можно построить таблицу предшествования T (точнее говоря, T(G)). Строки и столбцы таблицы однозначно поименованы основными и вспомогательными символами грамматики и дополнительным символом #. В клетки T(x,y) таблицы помещаются символы <,=,> по следующим правилам (в которых u и v могут быть произвольными строками): 1) T(x,y) содержит <, если G содержит правило вида A->uxBv такое, что существует непустой вывод строки, начинающейся с y, из символа B. 2) T(x,y) содержит >, если y - основной символ, и G содержит правило вида A->uBZv такое, что существуют непустой вывод строки, кончающейся на x, из символа B и (возможно, пустой) вывод строки, начинающейся с y, из символа Z (когда упомянутый последним вывод пуст, Z совпадает с y). 3) T(x,y) содержит =, если G содержит правило вида A->uxyv. 4) T(#,y) содержит <, если в G из аксиомы можно вывести строку, начинающуюся с y. 5) T(x,#) содержит >, если в G из аксиомы можно вывести строку, кончающуюся на x. Если T(x,y) содержит <, > или =, будем употреблять также обозначения x<y, x>y, x=y, соответственно (заметим, что одно- временно может быть x<y, x>y и x=y). G называется грамматикой простого предшествования, если каждое из множеств T(x,y) содержит не более одного элемента. G называется грамматикой слабого предшествования, если 1) каждое из множеств T(x,y) одновременно ссимволом > не может содержать ни символа <, ни символа =, 2) если G содержит два правила A->uXv и B->v, то не может быть ни X<B, ни X=B. Следующая грамматика для арифметических выражений типа a+a(aa+a) является обратимой грамматикой слабого (но не простого) предшествования. E->E+T \| T T->TF \| F F->(E) \| a Ниже приводится таблица предшествования для этой грамматики \| E T F a ( ) + # __\|___________________________ E \| = = T \| > > = > F \| > > > > a \| > > > > ) \| > > > > ( \|<= < < < < + \| <= < < < * \| = < < # \| < < < < < Алгоритм анализа. Ниже будем считать, что G - обратимая (т.е. не содержит разных правил с одинаковой правой частью) и приведенная (т.е. не содержит выводов вида A->B->...->A, и удовлетворяет некоторым другим простым условиям, которые обычно выполняются для естественным образом построенных грамматик). Пусть s - входная строка, дополненная в конце символом #, и m - вспомогательная строка (стек), вначале равная #. На каждом шаге работы имеется указатель на некоторый символ строки s (в начале работы указывается первый символ s) и указатель на последний символ стека m. Алгоритм состоит из этапов переноса и свертки. Пусть x - последний символ стека m, y - очередной символ во входной строке s. 1) Если x<y или x=y, то y переносится в m, и указатель на s переносится на следующий символ. 2) Если x>y, то в хвосте m производится свертка (т.е. замена правой части некоторого правила на его левую часть), если это возможно. Для грамматик простого предшествования такое правило (если оно есть) определяется однозначно. Для грамматик слабого предшествования это может быть не так: в этом случае надо заменять самую длинную правую часть. Если такого правила нельзя найти, то s нельзя вывести в G; 3) Если T(x,y) пусто, то s нельзя вывести в G (кроме случая x=E,y=#, в этом случае надо выйти из цикла и проверить стек на равенство с #E как ниже). Если таким образом удается обработать всю строку s и в конце работы m равен #E, где E - аксиома грамматики G, то делается вывод, что s можно вывести в G, а в противном случае - s не выводится в G. Добавлено через 2 минуты Всем здравствуйте! Ладно, я сразу признаюсь, что я чайник. У меня есть небольшие знания - однако же, их хватило на то, чтобы выполнить первые две лабораторные, да и то с помощью. Эту программу я просто-напросто не понимаю. Не прошу просто сделать ее за меня и прислать, что вы. Но я бы очень попросила хотя бы совет, как начать, а то я в ступоре. Спасибо. 0

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	26.05.2012, 06:59
	определение формальной грамматики 0

Грамматики простого и слабого предшествования

Решение