Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.72/25: Рейтинг темы: голосов - 25, средняя оценка - 4.72
2 / 2 / 1
Регистрация: 30.12.2010
Сообщений: 91
1

Конструирование транслятора для модельного языка. Литература по LEX/YACC

10.03.2012, 21:13. Показов 5001. Ответов 12
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Простите, не знал куда тему приткнуть.
Ищу литературу по LEX/YACC. Софт, книги и т.д.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
10.03.2012, 21:13
Ответы с готовыми решениями:

Lex и Yacc
Привет всем!=) может кто-нибудь кинуть литературу по Lex и Yacc, уж очень надо=) заранее благодарен=)

Литература для языка C
Подскажите пожалуйста полезную литературу для изучения языка С c нулевого уровня!

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

12
 Аватар для aw_rabbit
153 / 110 / 0
Регистрация: 08.02.2012
Сообщений: 202
10.03.2012, 21:34 2
Почему LEX/YACC?
Есть еще coco/r и antlr. Про coco неплохо написано в книге Мозгового М. В. "алгоритмы, языки, автоматы, компиляторы". Плюс еще инфа с сайта, но на английском. Вся теория в книге дракона - Ахо Компиляторы, принципы, технологии и инструменты от 2008 г.
1
2 / 2 / 1
Регистрация: 30.12.2010
Сообщений: 91
10.03.2012, 21:40  [ТС] 3
2. Выполняющий курсовую работу должен решить для себя, как он будет строить лексический и синтаксический анализаторы: самостоятельно (вручную) или автоматизированным методом (с использованием специализированного ПО- рекомендуются программы LEX или YACC). Автоматизированный метод проще, но требует от автора работы времени на освоение специализированного ПО. Возможно сочетать оба метода: например, построить лексический анализатор с помощью программы LEX, а синтаксический – вручную.

Вот почему. Но спасибо за информацию. Лишней не будет.
0
 Аватар для aw_rabbit
153 / 110 / 0
Регистрация: 08.02.2012
Сообщений: 202
10.03.2012, 21:52 4
YACC

Проблема не в том чем, а главное какая грамматика. Если понадобится отладка, т.е. разрешение конфликтов, то более продвинутые средства могут быть полезнее. Но лексический пишется в 100 -200 строк обычно, так что генерировать только лексер без парсера смысла нет.

У antlr есть хороший отладчик, но с ним долго разбираться. Еще antlr строит ast.
Coco/r генерирует код синтаксического анализатора методом рекурсивного спуска, т.е. сразу понятно что и как в грамматике странслировалось в парсер.
1
2 / 2 / 1
Регистрация: 30.12.2010
Сообщений: 91
10.03.2012, 22:12  [ТС] 5
<Программа> ::= <Объявление переменных> <Описание вычислений>.
<Описание вычислений> ::= Begin <Список присваиваний> End
<Объявление переменных> ::= Var <Список переменных> :Integer;
<Список переменных> ::= {/<Идент>[,]/}
<Список присваиваний>::= {<Присваивание>}
<Присваивание> ::= <Идент> = <Выражение>;
<Выражение> ::= [-]<Подвыражение>
<Подвыражение>:: = <произведение> {( + | -) <произведение>}
<произведение>:: = <множитель> { (* | /)<множитель>}
<множитель>:: = <операнд> | (<выражение>)
<Операнд> ::= <Идент> | <Const>
<Идент> ::= {/<Буква>/}
<Const> ::= {/<Цифра>/}
<Буква>::= a|...|z
<Цифра> ::= 0|1|…|9


И ещё нужно добавить конструкцию языка высокого уровня
WHILE ( <Выражение> )
<Оператор>


Как разумней начать делать?
0
Каратель
Эксперт С++
6610 / 4029 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
10.03.2012, 22:16 6
Цитата Сообщение от maxon56 Посмотреть сообщение
Как разумней начать делать?
читаешь ман по yacc/lex и делаешь
1
 Аватар для aw_rabbit
153 / 110 / 0
Регистрация: 08.02.2012
Сообщений: 202
11.03.2012, 00:07 7
Как разумней начать делать?
1. Посмотреть на грамматику. Все генераторы реализованы либо как LL (нисходящий разбор) либо как LR (восходящий разбор) анализаторы. Т.е. на грамматику будут накладываться определенные требования. Нельзя просто дать генератору любую грамматику и больше ни о чем не беспокоится - она должна соответствовать типу анализатора. Если не соответствует, то ее немного редактируют. В документации этот раздел называется "разрешение конфликтов".

2. Выбрать генератор. Правила, которыми описаны литералы (константа, переменная, число, строка) генерируют лексер. Все остальные -парсер. Обычно язык генератора сильно приближен к БНФ, так что прям в таком виде можно ему скармливать.

3. Пишется грамматика языка на который транслируют. Можно просто для себя набросать. Дальше нужно разобраться с атрибутами, т.е. грамматика из задания добавляется атрибутами. В доках к генераторам это называется "семантические действия". В книгах - синтаксически управляемая трансляция. Т.е. если у нас правило S->A := B на паскале и нам нужно перевести его например в С как S->A=B, то с атрибутами будет так S<str>->A<s1> := B<s2> { str=s1+"="+s2+"\n";}. str это просто строка с текстом нового кода. Тут мы ничего не вычисляем, поэтому все просто. С атрибутами нужно разобраться в любом случае- что в ручном что в автоматизированном варианте. Все генераторы генерируют лексер и парсер, а транслятор получается дописыванием семантических действий в грамматику.

Добавлено через 3 минуты
И ещё нужно добавить конструкцию языка высокого уровня
<Описание вычислений> ::= Begin {<Опреатор>} End
<Оператор>::=<Список присваиваний> | <Цикл>
Это с одним действием, т.е. дальше без вложенности begin/end

Добавлено через 3 минуты
PS: еще одна гадость -проверка на семантические ошибки. Т.е. проверить что переменная объявлена, что объявлена 1 раз, что типы соответствуют в выражениях и т.д. Делается тоже через атрибуты и семантические правила.
1
 Аватар для САШУЛЬКА11117
0 / 0 / 0
Регистрация: 13.02.2011
Сообщений: 71
12.03.2012, 20:57 8
это же банально.. лучше скажите как это программно реализовать
0
 Аватар для aw_rabbit
153 / 110 / 0
Регистрация: 08.02.2012
Сообщений: 202
12.03.2012, 21:04 9
Цитата Сообщение от САШУЛЬКА11117 Посмотреть сообщение
это же банально.. лучше скажите как это программно реализовать
Легко. Лексер - детерминированный конечный автомат, парсер - рекурсивный спуск, транслятор - синтаксически управляемая трансляция.
0
 Аватар для САШУЛЬКА11117
0 / 0 / 0
Регистрация: 13.02.2011
Сообщений: 71
12.03.2012, 21:05 10
сколько много новых слов
0
 Аватар для aw_rabbit
153 / 110 / 0
Регистрация: 08.02.2012
Сообщений: 202
12.03.2012, 22:04 11
Нашла у себя пример перевода в постфиксную запись. Генератор сосо, язык с++. На википедии в качестве примера какая то фигня выложена, а на самом сайте ну очень большой пример реализации C#. Так что может будет полезен.

C++
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <string>
#include <sstream>
#include <iostream>
#include <fstream>
#include <vector>
 
COMPILER expr 
 
 
int toInt(const std::wstring& strbuf)
{
    std::wstringstream converter;
    int value = 0;
 
    converter << strbuf;
    converter >> value;
    return value;
}
 
std::wstring toString ( int Number )
{
  std::wostringstream ss;
  ss << Number;
  return ss.str();
}
 
 
IGNORECASE
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".
digit = "0123456789".
cr  = '\r'.
lf  = '\n'.
tab = '\t'.
 
TOKENS
ident  = letter {letter | digit | "_"}.
number = digit {digit}.
 
COMMENTS FROM "/*" TO "*/" NESTED
COMMENTS FROM "//" TO cr lf
 
IGNORE cr + lf + tab
 
PRODUCTIONS
 
  expr (.std::wstring str;.) = (.std::wstring s,s1,s2,s3,s4; .) 
                  ident (.s1=t->val;.)":=" NumExpr<s2> ";" (. str+=s1; str+=s2; str+=L":=\n";.)
                  {ident(.s3=t->val; s4=L"";.)":=" NumExpr<s4> ";" (. s+=s3;  s+=s4; s+=L":=\n"; .)}
                  (.
                    str+=s;
                    std::wofstream outfile ("out.txt", std::ios_base::out);
                    outfile << str << std::endl;          
                    outfile.close();
                  .)
                  .
  
  NumExpr<std::wstring &str> = (.std::wstring s1,s2, op; .)
                        Term<s1> (.str+=s1;.)
                        { ("+" (.op=L"+";.)|"-" (.op=L"-";.)) NumExpr<s2>
                        (.
                            //str+=s1; 
                            str+=s2; str+=op;
                        .)
                        }.
  
  Term<std::wstring &str> =(.std::wstring s1,s2, op;.) 
                Multiplier<s1> (.str+=s1;.)
                { ("*" (.op=L"*";.)|"/"(.op=L"/";.)) Term<s2> 
                (.
                    //str+=s1; 
                    str+=s2; str+=op; 
                .)
                }.
  
  Multiplier<std::wstring &str> = 
                          ident (.str=t->val; .) 
                          | number (.str=t->val;.)
                          | (.std::wstring s; .) "(" NumExpr<s> ")" (.str=s;.).
  
  
END expr.
Добавлено через 2 минуты
вход
a:=b;
a:=a-5;
a:=9-5+2;
a:=2+3*4;
a:=(5-4)*(3+2);

выход
ab:=
aa5-:=
a952+-:=
a234*+:=
a54-32+*:=

make
all: translator


translator: Coco scanner.o parser.o main.o
g++ -o tr.exe scanner.o parser.o main.o

main.o: main.cpp
g++ -c main.cpp

scanner.o: Scanner.cpp Scanner.h
g++ -c Scanner.cpp -o scanner.o

parser.o: Parser.cpp Parser.h
g++ -c Parser.cpp -o parser.o

Coco: expr.atg
coco expr.atg

clean:
del Scanner.cpp Scanner.h Parser.cpp Parser.h
del Scanner.cpp.old Scanner.h.old Parser.cpp.old Parser.h.old
del scanner.o parser.o main.o
del translator

main
C++
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
#include <iostream>
#include <wchar.h>
#include "Parser.h"
#include "Scanner.h"
 
#include <string>
 
 
using namespace std;
 
main(int argc, char *argv[])
{
    if (argc == 2)
    {
        
        wchar_t *file  = coco_string_create(argv[1]);
 
        Scanner *scanner = new Scanner(file);
        Parser *parser   = new Parser(scanner);
        parser->Parse();
 
        delete parser;
        delete scanner;
        delete file;
 
        return 0;
    }
    
    else
    {
        cout << "Use: translator filename" << endl;
        return 1;
    }
}
1
 Аватар для САШУЛЬКА11117
0 / 0 / 0
Регистрация: 13.02.2011
Сообщений: 71
12.03.2012, 22:11 12
тот кто создавал эту тему, нечего тут не поймёт....
но от меня,спасибо))
0
 Аватар для aw_rabbit
153 / 110 / 0
Регистрация: 08.02.2012
Сообщений: 202
14.03.2012, 11:22 13
Чистая грамматика
Expr->ident := NumExpr ;
NumExpr-> Term {+|- NumExpr}
Term->Multiplier {*|/ Term}
Multiplier->ident|number| ( NumExpr)

Все что в <> атрибуты. Транслируются в параметры функции
Все что в (. .) семантические правила. При трансляции просто вставляются в код.

Отладка такого кода делится на 2 этапа:
1. Отладка самой грамматики. Тогда генератор ругается непонятными словами типа факторизация или левая рекурсия.
2. Отладка кода, который мы нагенерировали. Генератор не проверяет то что вы там написали в скобках, а честно их вставляет в код. Дальше дело за компилятором. Иногда чтобы понять что не так нужно залесть прямо в код.

Пример функции для первого правила:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Parser::expr() {
        std::wstring str;
        std::wstring s,s1,s2,s3,s4; 
        Expect(1);
        s1=t->val;
        Expect(3);
        NumExpr(s2);
        Expect(4);
        str+=s1; str+=s2; str+=L":=\n";
        while (la->kind == 1) {
            Get();
            s3=t->val; s4=L"";
            Expect(3);
            NumExpr(s4);
            Expect(4);
            s+=s3;  s+=s4; s+=L":=\n"; 
        }
        str+=s;
        std::wofstream outfile ("out.txt", std::ios_base::out);
        outfile << str << std::endl;          
        outfile.close();
            
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
14.03.2012, 11:22
Помогаю со студенческими работами здесь

Lex и YACC
Здравствуйте дорогие форумчане! Есть специалисты, разбирающиеся в LEX и YACC? Нужна ваша помощь в ЛС. Спасибо!!

Lex и Yacc
Дано задание: Транслятор произвольных логических выражений в ДНФ Разработать язык описания логических выражений , позволяющий : ...

Синтаксическая ошибка (Lex, Yacc)
Доброго времени суток. Пишу калькулятор при помощи Lex/Yacc. Сам счет происходит правильно, но после него вылезает синтаксическая ошибка. В...

Lex и YACC Конечные автоматы.
Пожалуйста, приведите простейшие примеры кода (любых) работоспособных конечных автоматов на LEX и YACC. И напишите, что они делают. ...

Lex&Yacc + iOS
Привет, у меня небольшой вопрос, не особо надеюсь что ктото поможеть, но все же https://github.com/MaxPatsy/iORC мой проект на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Новые блоги и статьи
Winforstrap или красявый дизайн своими руками на HTML+JS+Winform­s
anomal6 04.03.2025
Сидел тут вечером ковырял проект на MAUI, и как же глупо создаются пакеты MSIX и система обновлений пакета публикации, но не об этом. Бывает нужен современный дизайн программы а писать на MAUI,. . .
Формат данных для симуляции физики, посредством распространённы­­­­­­­х не обученных моделей.
Hrethgir 04.03.2025
Что-то как-то снова потерялось, зато катангенсы закатангесились в одном сообщении. На днях писал, что планирую для работы апгрейдить (на этот раз удачно) девайс для работы (конкретно - здоровья для,. . .
Концепция variadic
CoderHuligan 04.03.2025
Мне не очень нравится (а кому это нравится?) что у нас есть отдельно компилятор, отдельно линковщик, причем со своим собственным командным языком. При этом усложнении надо знать помимо языка. . .
Java Record или Kotlin Data Class: что лучше для неизменяемых данных
Wired 04.03.2025
Java Record и Kotlin Data Class — два мощных инструмента для обуздания неизменяемых структур данных, каждый со своим уникальным подходом к решению этой задачи. История их появления весьма. . .
Создание производительны­­­х API с Java и gRPC
Wired 04.03.2025
В мире микросервисной разработки вопрос производительности часто становится краеугольным камнем. И хотя REST API давно завоевал сердца разработчиков своей простотой и интуитивностью, при высоких. . .
Что нового в JDK 24
Wired 04.03.2025
JDK 24 — это настоящий прорыв в эволюции Java, который кардинально меняет правила игры. В этом релизе разработчики Oracle наконец-то довели до ума множество критически важных улучшений в. . .
Разработка блокчейн с использованием Java: смарт-контракты и dApp
Wired 04.03.2025
Погружаясь в мир блокчейн-разработки на Java, разработчик получает доступ к внушительному арсеналу инструментов. В отличие от Solidity, который "заперт" в экосистеме Ethereum, Java предоставляет. . .
WebAssembly в Kubernetes
stackOverflow 03.03.2025
В современной экосистеме облачных технологий WebAssembly (Wasm) становится все более значимым компонентом, предлагая уникальный подход к выполнению кода в распределенных системах. Эта технология. . .
GitHub Actions или Jenkins: Выбираем CI/CD платформу
stackOverflow 03.03.2025
Непрерывная интеграция и развертывание (CI/ CD) изменили подход к разработке программного обеспечения, превратив его в бесшовный процесс от написания кода до развертывания в продакшн. GitHub Actions и. . .
Автоматизация тестирования Pull Request в Kubernetes: Интеграция с GitHub Actions и GKE
stackOverflow 03.03.2025
Масштабные проекты с использованием Kubernetes требуют надежной системы тестирования изменений перед их внедрением в продакшн-среду. Традиционный подход с ручной проверкой Pull Request не справляется. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru