Описание тега context-free-grammar
В формальной теории языка контекстно-свободная грамматика (CFG) - это грамматика, на которую накладывается особое ограничение: левая часть (LHS) состоит из одного нетерминального символа. CFG могут представлять набор контекстно-свободных языков (CFL).
2
ответа
С грамматика составное утверждение
Я смотрел на грамматику C на K&R; и нашел это: compound-statement: { declaration-list opt statement-list opt } declaration-list: declaration declaration-list declaration statement-list: statement statement-list statement Это означает, что у нас не м…
14 май '14 в 20:54
1
ответ
Распознавать максимальный тип формального языка
В настоящее время я пытаюсь изучать и понимать формальные языки и грамматику. Я понимаю иерархию Хомского, но нашел задачу, в которой я не знаю, как они нашли решение. Задача: G=({S},{a,b},S,P) P={S->epsilon, S->aS, S->Sb} Каков максимальны…
01 фев '17 в 13:54
1
ответ
Можно ли выразить левый ассоциативный оператор таким образом, чтобы синтаксические анализаторы LL(1) могли его понять?
Я пытался реализовать нисходящий синтаксический анализатор LL(1) для языка калькулятора. Это позволяет нам только суммировать, вычитать, делить и умножать числа. Нет скобок. S -> A A -> B + A | B - A | B B -> int * B | int / B | int Посколь…
06 май '13 в 19:12
1
ответ
Лучший способ разобрать суффиксированные слова
Мне нужен парсер, который распознает часть речи в соответствии с последней буквой каждого слова. Я использовал Python, но я не уверен, что доступные парсеры CFG примут это. Давайте возьмем эсперанто слова, например. Все прилагательные оканчиваются н…
30 апр '15 в 13:46
1
ответ
Как разобрать контекстно-зависимую грамматику?
CSG похож на CFG, но символ сокращения кратен. Итак, могу ли я просто использовать анализатор CFG для анализа CSG с сокращением производства на несколько терминалов или нетерминалов? подобно 1. S → a bc 2. S → a S B c 3. c B → W B 4. W B → W X 5. W …
07 апр '15 в 02:22
2
ответа
Накачка леммы в контекстно-свободных языках
A = {0^a 1^b 2^c | a < b < c} Мне нужно показать, что A не является контекстно-свободным. Я предполагаю, что для этого мне нужно использовать Лемму прокачки, но как?
04 ноя '10 в 10:01
1
ответ
Удаление нулевых произведений из контекстно-свободной грамматики
X -> zZ|yW|WW Y->Z Z->X|ε W->Y|X Буду ли я прав, полагая, что в качестве Y только Z в качестве своего терминала ε переходит к Y, давая: X -> zZ|yW|WW Y->Z|ε Z->X W->Y|X затем? X -> zZ|yW|WW|z Y->Z Z->X W->Y|X
12 дек '14 в 13:17
1
ответ
Как проверить тексты, не соответствующие грамматике Instaparse (Clojure)?
Я написал проект для разбора строк с использованием контекстно-свободной грамматики в Instaparse (Clojure). Теперь я хотел бы проверить несколько строк ввода для их результатов анализа. Некоторые входные строки могут не вписываться в грамматику. До …
13 окт '14 в 11:28
1
ответ
Нахождение контекстно-свободной грамматики
У меня были серьезные проблемы с этой задачей: L = {w element of {a,b}* | the number of a's plus 2 times the number of b's modulo 5 in w is 0} Я думал о: S -> ε S -> abbS S -> babS S -> bbaS S -> aaaaaS S -> aaabS так далее... Но э…
30 окт '14 в 19:29
1
ответ
Генерация CFG для языка
Рассмотреть язык {anbmcp | n <= p OR m <= p} создать CFG для этого языка.Я начал это с S -> aA | aB, но я не уверен, как мне поступить при определении A или B. "ИЛИ" кажется довольно сложным для включения в определение языка, так как нет необх…
04 ноя '15 в 17:32
1
ответ
Как перевести на antlr4 грамматику ObjectLiteral[Выход]?
Я пытаюсь перевести грамматику es6 с: https://tc39.github.io/ecma262/ и https://gist.github.com/rbuckton/0d8c1f1c607f52f5ae37 Моя проблема в том, что многие объявления содержат что-то вроде этого: ObjectLiteral[Yield] : { } { PropertyDefinitionList[…
12 авг '16 в 20:34
1
ответ
Преобразование заданной грамматики неоднозначного арифметического выражения в однозначный LL(1)
В этом плане у меня есть курс по компиляторам, и в настоящее время мы изучаем синтаксис - различные грамматики и типы синтаксических анализаторов. Я столкнулся с проблемой, которую не могу точно понять, или, по крайней мере, не могу убедиться, что д…
26 мар '16 в 12:51
1
ответ
Какие грамматики могут быть проанализированы с использованием рекурсивного спуска без возврата назад?
Согласно "Парсеру рекурсивного спуска" в Википедии, рекурсивный спуск без обратного отслеживания (так называемый предиктивный анализ) возможен только для грамматик LL(k). В другом месте я читал, что реализация Lua использует такой парсер. Тем не мен…
21 авг '17 в 12:02
2
ответа
Построение автомата пуш-ап из контекстно-свободной грамматики
Из этого раздела вики-статьи о КПК я получил приблизительное представление о процессе создания КПК из данного CFG. То, что эта статья не проясняет, является шагом, необходимым, когда есть несколько производственных правил для одного нетерминала. Нап…
04 ноя '13 в 06:29
1
ответ
Распознающая сила "современных" регулярных выражений
Какой класс языков действительно распознают современные современные регулярные выражения? Всякий раз, когда существует группа захвата неограниченной длины с обратной ссылкой (например, (.*)_\1) регулярное выражение теперь соответствует нерегулярному…
30 янв '11 в 03:33
1
ответ
Упрощение лямбда-производств, унарных правил и бесполезных символов грамматики
Я знаю, что это не общий вопрос, но я хотел бы знать, как это сделать, используя пример, над которым я уже немного работал.. Однажды сказал это: У меня есть следующая грамматика. Я пытался упростить его, но я не уверен в его правильности. Может ли к…
16 окт '16 в 14:43
1
ответ
Это сделает мою грамматику неоднозначной?
Хорошо, допустим, у меня есть следующая грамматика <Exp> -> <Term> <EXp> -> <Term> {<AddOp> <Exp>} <Term> -> <Factor> {<MultOp> <Term>} <Factor> -> <id> | <no>…
01 май '17 в 18:11
0
ответов
csp-алгоритм для контекстно-свободных грамматик
Я пытаюсь решить CSP (Constraint-Satisfaction-Problem), которая основана на произвольных контекстно-свободных грамматиках. Быстрый пример: допустим, у нас есть контекстно-свободная грамматика со следующими правилами производства: S->A, S->B, S->AB, …
26 мар '15 в 11:37
1
ответ
Алгоритм проверки грамматики против другой грамматики в ll(1)
Мне нужен алгоритм, который проверяет, является ли язык G1 подмножеством языка G2 или нет. (Предположим, что G1 и G2 - две грамматики LL(1) с одинаковыми алфавитами, правила производства которых имеют форму A -> aB или A -> a, а "a" не является эпси…
20 дек '15 в 17:10
1
ответ
Находить LL(1) грамматику?
Как найти грамматику LL(1) для языка: L = am bn cm + n Где m и n элементы натуральных элементов? Моя контекстно-свободная грамматика: S → AB A → acA | переменный ток B → bcB | До нашей эры Может ли кто-нибудь сказать мне, если я на правильном пути? …
02 дек '13 в 02:28