Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.76
maxon56
2 / 2 / 1
Регистрация: 30.12.2010
Сообщений: 91
#1

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

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

Простите, не знал куда тему приткнуть.
Ищу литературу по LEX/YACC. Софт, книги и т.д.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.03.2012, 21:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Конструирование транслятора для модельного языка. Литература по LEX/YACC (C++):

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

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

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

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

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

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

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

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

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

У antlr есть хороший отладчик, но с ним долго разбираться. Еще antlr строит ast.
Coco/r генерирует код синтаксического анализатора методом рекурсивного спуска, т.е. сразу понятно что и как в грамматике странслировалось в парсер.
1
maxon56
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
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
10.03.2012, 22:16 #6
Цитата Сообщение от maxon56 Посмотреть сообщение
Как разумней начать делать?
читаешь ман по yacc/lex и делаешь
1
aw_rabbit
147 / 104 / 6
Регистрация: 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
147 / 104 / 6
Регистрация: 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
147 / 104 / 6
Регистрация: 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
147 / 104 / 6
Регистрация: 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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.03.2012, 11:22
Привет! Вот еще темы с ответами:

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

Написание транслятора/парсера с одного языка на другой - Программирование
Добрый день! Возникла необходимость написать транслятор программного кода (возможно, вы будете смеяться ) из Visual Basic Application...

Написание транслятора с языка Паскаль на язык ассемблер (FASM) - Assembler
Здравствуйте, поскольку в программировании - новичок, очень большой проблемой стало следующее задание - написание транслятора с языка...

Нужна литература для изучения языка - Turbo Pascal
Народ я в написании программ новичок, ну вообщем почти полный ноль, ещё в web (html,php....) понимаю, а здесь я только начал, короче,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.03.2012, 11:22
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru