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

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

10.03.2012, 21:13. Показов 4994. Ответов 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 нулевого уровня!

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

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

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
14.03.2012, 11:22
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
14.03.2012, 11:22
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Элементы алгоритмизации
hw_wired 28.01.2025
Основы алгоритмизации В современном мире алгоритмы играют фундаментальную роль в развитии информационных технологий и программирования. Понимание основ алгоритмизации является ключевым элементом в. . .
Человек и информация
hw_wired 28.01.2025
Введение: роль информации в познании мира В современном мире информация играет фундаментальную роль в процессе познания окружающей действительности. Она представляет собой совокупность сведений об. . .
Компьютер и информация
hw_wired 28.01.2025
Эволюция вычислительных машин История развития вычислительной техники начинается задолго до появления первых электронных устройств. Человечество всегда стремилось упростить процесс вычислений и. . .
Информационные технологии
hw_wired 28.01.2025
Введение в современные технологии работы с информацией В современном мире информационные технологии стали неотъемлемой частью практически всех сфер человеческой деятельности. Они существенно. . .
Информация вокруг нас
hw_wired 28.01.2025
Основные понятия информации В современном мире понятие информации является фундаментальным и охватывает практически все сферы человеческой деятельности. Информация представляет собой совокупность. . .
Компьютер для начинающих
hw_wired 28.01.2025
Введение в мир компьютерных технологий В современном мире информация стала одним из важнейших ресурсов человечества, определяющим развитие общества и технологий. Наша жизнь неразрывно связана с. . .
[golang] 189. Rotate Array
alhaos 28.01.2025
Повороты рукоятки, целочисленный слайс нужно сдвинуть на целое положительное число. Мне очень нравится решение на GO / / https:/ / leetcode. com/ studyplan/ top-interview-150/ package topInterview . . .
КуМир: решение задач на матрицы
bytestream 28.01.2025
КуМир представляет собой среду для обучения программированию, которая включает в себя мощные инструменты для работы с матрицами. Матрица в программировании - это двумерный массив, состоящий из. . .
КуМир: решение задач на строки
bytestream 28.01.2025
В системе программирования КуМир работа со строковыми данными является одним из важнейших аспектов создания программ. Строки представляют собой последовательности символов, заключенные в кавычки,. . .
КуМир: решение геометрических задач
bytestream 28.01.2025
Программирование геометрических задач в среде КуМир становится всё более актуальным в обучении школьников и студентов. КуМир — это разработанная в России обучающая программная среда, предназначенная. . .
КуМир, исполнитель Водолей: Задачи и решения
bytestream 28.01.2025
КуМир — это образовательная среда для обучения программированию. Она предлагает пользователям разнообразные инструменты для разработки и отладки программ, что особенно ценно для студентов и. . .
КуМир, исполнитель Чертежник: Решение задач
bytestream 28.01.2025
КуМир (Комплект Учебных МИРов) представляет собой образовательную среду для обучения основам программирования и алгоритмизации. Исполнитель Чертежник работает на координатной плоскости, где может. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru