4
голосов
1ответов
2674 просмотров

Левая рекурсия исключения для E: = EE + | EE- | id

Как устранить левую рекурсию для следующей грамматики? E := EE+|EE-|id Используя обычную процедуру: A := Aa|b переводится как: A := b|A' A' := ϵ| Aa Применяя это к исходной грамматике, мы получаем: A = E, a = (E+|E-) and b = id Следовательно: E := id|E' E' := ϵ|E(...

2
голосов
8ответов
2903 просмотров

Context Free Grammar for Unary Addition

Given an alphabet of 1s I want to parse addition of the form 1^k + 1^j = 1^k+j This is pretty easy to represent with a pushdown automaton simply by pushing a 1 on to the stack on each of the first two 1s, and then popping on the last set of 1s. However, I can't seem to figure out how to repre...

9
голосов
3ответов
5321 просмотров

self-taught compiler courses / good introductory compiler books?

Does anyone know of online course / university lectures that comprise a typical compiler course? I've had theory of computing but unfortunately my school didn't offer a course in compiler construction. I know there are lectures out there; I was hoping for recommendations for particularly good...

3
голосов
2ответов
560 просмотров

Optional vs. mandatory terminators in context-free grammar definition

In a book chapter about compilers, there's the following grammar definition and example code. ... statement: whileStatement | ifStatement | ... // Other statement possibilities | '{' statementSequence '}' whileStatement: 'while' '(' expression ')' statement ifSta...

3
голосов
2ответов
685 просмотров

Implementing a XML translator using XML's EBNF

I'm contemplating the idea of implementing a XML translator using a compiler generator, based on the W3C's XML 1.1 spec, which includes a complete EBNF grammar. More precisely, I plan to use Qi-YACC because I want to learn this tool. It will be my first foray into using any compiler-compiler. T...

1
голосов
2ответов
203 просмотров

Converting a CFG to IL

I build a CFG out of an arbitrary IL and want to convert that CFG back to IL. The order of the vertices in the CFG is of course not equal to the order of the original IL instructions. This is fine but overcomplicates some stuff. Imagine: Jump 'B' 'C': Return 'B': Jump 'C' This would result in...

3
голосов
2ответов
1366 просмотров

Pumping lemma for CFLs

My question is: Let L = { x in {a,b}* | x has an equal number of a's and b's} I know this is a context free language because I can create a grammar for it (e is epsilon): S -> aX | bY | e X -> bS | aXX Y -> aS | bYY You can also prove it is context free by using the fact that a co...

1
голосов
4ответов
697 просмотров

Parsing a Gmail-style advanced search syntax?

I want to parse a search string similar to that provided by Gmail using Perl. An example input would be "tag:thing by:{user1 user2} {-tag:a by:user3}". I want to put it into a tree structure, such as {and => [ "tag:thing", {or => [ "by:user1", "by:user2", ]}, ...

2
голосов
2ответов
1347 просмотров

Как я могу устранить левую рекурсию в следующей грамматике?

Вот грамматика, которая должна описывать язык, состоящий из вложенных фигурных скобок с запятыми в качестве разделителей: L ::= {L} | L,L | Еще несколько примеров строк, которые, как мне кажется, грамматика примет и отклонит: Принять: {,{,,{,}},,{,}} {{{{}}}} {,{}} Отклонить: ...

77
голосов
1ответов
25576 просмотров

Разница между парсером LL и рекурсивным спуском?

Я недавно пытался научить себя, как работают парсеры (для языков / контекстно-свободных грамматик), и большая часть из них, кажется, имеет смысл, за исключением одного момента. Я сосредотачиваю свое внимание, в частности, на грамматиках LL (k) , для которых двумя основными алгоритмами являются ...

7
голосов
1ответов
2151 просмотров

Как я могу определить грамматику файла INI с помощью BNFC?

http://www.cs.chalmers.se/Cs / Исследования / Языковые технологии / BNFC / как мне написать свой помеченный BNF, чтобы заставить BNFC сгенерировать для меня анализатор INI? У меня пока только __O! entrypoints File ; comment "#" ; token ID ( letter | digit | ["-_'"] )+ ; Ini. File :...

4
голосов
6ответов
13194 просмотров

Как я могу построить грамматику, которая порождает этот язык?

Я готовлюсь к тесту по конечным автоматам и грамматике, и у меня возник вопрос: Construct a grammar that generates L: L = {a^n b^m c^m+n|n>=0, m>=0} Я считаю, что мои постановки должны соответствовать следующему: S->aA | aB B->bB | bC C->cC | c Here's where I...

0
голосов
2ответов
365 просмотров

Синтаксис, подобный регулярному выражению, или CFG для создания декартова произведения объединенных строковых переменных и литералов

Я пишу симулятор и хотел бы проводить исследования, вызывая множество экземпляров симулятора, используя разные наборы аргументов командной строки. Я прочитал этот вопрос и несколько других, и они кажутся близкими, но я На самом деле я не ищу случайные данные, удовлетворяющие определенному регу...

7
голосов
3ответов
3338 просмотров

Бесконтекстная грамматика, описывающая регулярные выражения?

Я пытаюсь написать механизм регулярных выражений. Я хотел бы вручную написать парсер рекурсивного спуска. Как бы выглядела контекстно-свободная грамматика без левой рекурсии для языка регулярных выражений (а не языков, которые могут быть описаны регулярными выражениями)? Не было бы проще перефак...

65
голосов
8ответов
25319 просмотров

Какие языки программирования контекстно-свободны?

Или, если быть более точным: какие языки программирования определяются контекстно-свободной грамматикой? Насколько я понимаю, C ++ не является контекстно-свободным из-за таких вещей, как макросы и шаблоны. Моя интуиция подсказывает мне, что функциональные языки могут быть контекстно-свободным...

4
голосов
3ответов
772 просмотров

Ищу интерактивную утилиту для создания контекстно-свободных грамматик парсера

Мне нужна утилита, с помощью которой я могу предоставить фрагмент текста (в текстовом поле) и поэкспериментировать с грамматикой парсера (путем редактирования аналогичного BNF) и структурой токенов, пока я могу видеть, как будет выглядеть дерево синтаксического анализа ( и если он не может проан...

1
голосов
2ответов
879 просмотров

Разделение строки (особенно в Java с java.util.regex или чем-то еще)

Кто-нибудь знает, как разбить строку на символ с учетом его escape-последовательности? Например, если символ ':', «a: b» разделяется на две части («a» и «b»), тогда как «a: b» не разделяется вообще. Я думаю, что это сложно (невозможно?) сделать с регулярными выражениями. Заранее благода...

6
голосов
8ответов
301 просмотров

Почему он-лайн парсеры, кажется, останавливаются на регулярных выражениях?

Мне давно интересно, почему, похоже, нет парсеров, скажем, для BNF , которые действуют как регулярные выражения в различных библиотеках. Конечно, есть такие вещи, как ANTLR , Yacc и многие другие, которые генерируют код , который, в свою очередь, может анализировать CFG , но, похоже, не...

0
голосов
3ответов
3990 просмотров

Как я могу написать свою контекстно-свободную грамматику?

Я пытаюсь написать CFG по алфавиту Σ = {a,b} для всех слов, начинающихся и заканчивающихся одним и тем же числом a, с хотя бы одним b посередине. Теперь я понимаю базовую концепцию CFG, переменных, производственных правил и т. д. К сожалению, у меня закончились идеи для написания вышеупомянут...

3
голосов
5ответов
3722 просмотров

Нерегулярный контекстно-свободный язык и бесконечное количество регулярных подъязыков

У меня была работа в университете, в которой говорилось: «Демонстрирует, что нерегулярный язык L = {0 ^ n 1 ^ n: n natural} не имеет бесконечных регулярных подъязыков». Я продемонстрировал это от противного. Я в основном сказал, что существует язык S, который является подъязыком L, и это о...

1
голосов
3ответов
3840 просмотров

Конвертация контекстно-свободной грамматики

может ли кто-нибудь сообщить мне, существует ли какое-либо программное обеспечение для преобразования нормальной формы Хомского в Форма Бэкуса – Наура и наоборот?

10
голосов
3ответов
1974 просмотров

Действительно ли «регулярное выражение» в современных языках программирования «контекстно-зависимая грамматика»?

С годами сопоставление с образцом "регулярных выражений" становится все более и более мощным, и я задаюсь вопросом: действительно ли это просто сопоставление контекстно-зависимой грамматики? Является ли это вариацией / расширением контекстно-свободного грамматического сопоставления? Где это сейч...

97
голосов
8ответов
110286 просмотров

Обычные и контекстно-свободные грамматики

Я готовлюсь к тесту по языкам вычислений , и есть одна идея, что у меня проблемы с головой. Я понял, что обычные грамматики проще и не могут содержать двусмысленности, но не могут выполнять множество задач, необходимых для языков программирования. Я также понял, что контекстно-свободные г...

4
голосов
3ответов
2177 просмотров

Замыкания и контекстно-свободные грамматики

Я просматриваю свой учебный план на уроке теоретической информатики, и в заголовке контекстно-свободных грамматик он перечисляет «закрывающие свойства». Я просмотрел свой учебник по этому предмету и нашел совсем немного. То немногое, что в нем есть, сейчас немного выше моей головы (я еще не прош...