Вопросы по теме 'context-free-grammar'
Удаление левой рекурсии в контекстно-свободной грамматике
Попытка выяснить удаление левой рекурсии в контекстно-свободных грамматиках. Я привык к определенным формам, но этот меня немного сбивает с толку.
S --> S {S} S | (A) | a
A --> {S} A | epsilon
Мне также нужно разработать приличный...
2465 просмотров
schedule
23.11.2021
Контекстно-свободная грамматика для этого языка
Я работаю над некоторыми материалами для подготовки к экзаменам и застрял над этой проблемой.
Покажите свободную от контекста грамматику для L = {w e {a, b} *: w = wR, и за каждым a сразу следует a b}.
wR - это w в обратном порядке. Итак, в...
1082 просмотров
schedule
25.11.2021
Правильность нормальной формы Хомского
У меня есть эти постановки:
S->aSb
S-> eps (eps=empty string)
Я должен применить нормальную форму Хомского
Мои рассуждения:
1) исключить правила eps. Дано:
S->aSb
S-> eps
Я получил:
S->ab
S->aSb...
736 просмотров
schedule
13.09.2021
BNF Grammar для структур в стиле Python
Я пытаюсь использовать простую грамматику для анализа структур, подобных Python, это то, что я мог бы придумать для списка / набора
list : '[' atom ( ',' atom)* ']'
set : '(' atom ( ',' atom)* ']'
atom : 'a'..'z' | 'A'..'Z'
| '[' list ']'...
1509 просмотров
schedule
17.10.2021
Является ли следующая языковая грамматика свободной от контекста?
Для n> = 0 является ли данная грамматика (a ^ na ^ na ^ n) контекстной? Я пробовал использовать лемму о перекачке, и результат был, нет, это не контекстно-зависимый.
1081 просмотров
schedule
13.11.2021
Пример грамматики Bison для объявления и использования функции
Может ли кто-нибудь привести пример грамматики Bison для объявления функций и использования функций, чтобы синтаксический анализатор вырабатывал ошибку, если количество аргументов в объявлении и использовании различается?
695 просмотров
schedule
13.10.2021
Есть ли у них какой-либо алгоритм синтаксического анализа предложений с использованием биграммной вероятности?
Я знаю, что алгоритм CKY может анализировать предложения с использованием вероятностей производственных правил.
Есть ли какой-нибудь алгоритм синтаксического анализа предложений, который я могу использовать, если я знаю только вероятности биграмм...
202 просмотров
schedule
23.09.2021
Почему праворекурсивная грамматика не подходит для анализа LR (k) снизу вверх?
Почему праворекурсивная грамматика не подходит для анализа LR (k) снизу вверх?
Я знаю, что парсинг снизу вверх начинается с листьев и наращивается до корневого узла, тогда как сверху вниз начинается с корня и идет вниз, провел небольшое...
1295 просмотров
schedule
07.09.2021
Сделает ли это неоднозначной мою грамматику?
хорошо, допустим, у меня следующая грамматика
<Exp> -> <Term>
<EXp> -> <Term> {<AddOp> <Exp>}
<Term> -> <Factor> {<MultOp> <Term>}
<Factor> -> <id> |...
22 просмотров
schedule
17.11.2021
указание грамматического правила появления в любом порядке, но не более одного раза
Скажем, у меня есть три символа A, B, C.
В ANTLR, как мне указать, что в предложении A, B и C могут появляться не более одного раза и что они могут встречаться в любом порядке. (Например, ABC, BCA оба законны)
Я пытался
(A | B | C)*
зная,...
262 просмотров
schedule
04.09.2021
Что не так с этой грамматикой ANTLR?
Я хочу разобрать выражения запроса, которые выглядят так:
Имя человека =% John%
(Имя человека = Джон% и адрес =% Онтарио%)
Person Fullname_3 = "Джон С. Смит"
Но я новичок в Antlr4 и даже не могу понять, как разобрать...
73 просмотров
schedule
20.09.2021
Различные способы объявления LOOKAHEAD в JAVACC
Я понял грамматику Javacc, чтобы написать парсер, где я нашел строку, которая говорит как
Options : { LOOKAHEAD=3; }
Мне было интересно, что такое LOOKAHEAD и есть ли другие способы объявить lookahead?
249 просмотров
schedule
16.10.2021
Генерация строк из контекстно-свободных грамматик
Проблема заключается в реализации алгоритма, который генерирует все строки длиной от l до r из заданной контекстно-свободной грамматики G .
Я придумал простой подход: запустить BFS на грамматическом графе, запоминая состояния. Но он не...
1775 просмотров
schedule
04.02.2022
Как работает алгоритм CYK?
Я должен проверить, может ли строка быть получена из данного контекста без контекста, который находится в нормальной форме Хомского. Я использую С++.
В статье Википедии, посвященной алгоритму CYK, есть очень хороший псевдокод , но я не могу я...
4549 просмотров
schedule
24.02.2022
Удаление производства эпсилон из контекстно-свободной грамматики
У меня просто проблемы с одной частью грамматики, которая гласит:
C -> CBA | epsilon
После того, как я удалю продукцию epsilon, я получаю:
C -> CBA | CB | BA | B | A
Я в замешательстве, правильно это или нет. В грамматике B...
2031 просмотров
schedule
23.02.2022
Преобразование двусмысленного языка в однозначный
Мне дали домашнее задание преобразовать следующую грамматику в недвусмысленную.
A --> B
A --> ε
B --> B @ B
B --> STRING
B --> DOUBLE(STRING)
где A и B — нетерминалы, а STRING и DOUBLE — нетерминалы.
Я могу сделать вывод,...
901 просмотров
schedule
23.02.2022
Узнать сгенерированный язык, учитывая контекстно-свободную грамматику?
Должен ли я вручную применять продукционные правила, чтобы узнать язык, сгенерированный этой грамматикой? Это утомительно, есть ли какой-нибудь трюк/совет, чтобы ускорить процесс?
G = {{S, B}, {a, b}, P, S}
P = {S -> aSa | aBa, B -> bB |...
3846 просмотров
schedule
02.03.2022
Построение набора следования
Создавая первый набор для данной грамматики, я заметил сценарий, не описанный в моем справочнике по алгоритму.
А именно, как можно вычислить набор слежения для нетерминала с таким правилом.
<exp-list_tail> --> COMMA <exp>...
798 просмотров
schedule
03.03.2022
Вычисление первого и последующего набора грамматики
ниже приведена грамматика, которую я использую для языка калькулятора, и моя попытка найти следующий набор и первый набор грамматики.
Я хотел бы помочь в выяснении того, что я делаю неправильно, пытаясь понять эти наборы, потому что я чувствую, что...
304 просмотров
schedule
09.03.2022
Бизон уменьшить/уменьшить конфликт
Я получаю конфликт уменьшения/уменьшения в следующей грамматике (отрывок)
declaration : type list_of_id
list_of_id : ID
| list_of_id ',' ID
;
type...
137 просмотров
schedule
15.03.2022