Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/11: Рейтинг темы: голосов - 11, средняя оценка - 5.00
SysUnit
36 / 33 / 1
Регистрация: 11.01.2013
Сообщений: 370
1

Лексический анализатор. Если бы я был компилятором

07.06.2013, 22:39. Просмотров 2051. Ответов 30
Метки нет (Все метки)

Доброго времени суток!
Хочестся понять как осуществить лексический анализ языка программы.
Для конкретности: вычисления суммы квадратов компонент массива чисел.
Pascal
1
2
3
s:=0;
for i := 0 to N-1 do
  s := s + sqr(a[i]);
Понять как если бы я был компилятором... понять алгоритм и разобрать этот "игрушечный" пример руками.
Не знаю как подступиться к задаче. Просьба помочь...
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.06.2013, 22:39
Ответы с готовыми решениями:

Как писать лексический анализатор?
Лучше места, чем "технологии", для темы не нашёл, но если всё таки не туда, то просьба к...

лексический анализатор
Добрый День помогите сделать лексический анализатор который считывал из текстового файла текст,...

лексический анализатор
задача на нахождение чисел в файле , помогите преобразовать функцию copy в задаче, без нее нужно...

Лексический анализатор
В общем такое дело, делаю лабу и немного запуталась. Сделала я строку поиска и генерацию слов по...

Лексический анализатор
есть задание: в принципе, трудностей, как его реализовывать, нет. считываем слово, сравниваем...

30
Igor3D
1228 / 595 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
08.06.2013, 12:09 2
"Лексический анализ" - может означать очень многое. Часто подразумевается "распарсить" входной текст, напр первая строка разлагается на массив/контейнер "лексем"
s
:=
0
;

Каждой лексеме присваивается тип (напр s переменная, := операция), ну и дальше это или выполняется (интерпретатор) или строится код (компилятор)
0
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,021
Записей в блоге: 22
08.06.2013, 20:26 3
Цитата Сообщение от Igor3D Посмотреть сообщение
"Лексический анализ" - может означать очень многое. Часто подразумевается "распарсить" входной текст
Что ещё может означать "лексический анализ"?

ТС, по-видимому, знает, что такое граматики, автоматы, которые распознают (иными словами, парсят) эти самые граматики и т.п.
В чём вопрос заключается конкретно? Должен ли ответ ориентироваться на конкретный язык Pascal или нет?
Я не понял, спрашивается о том, как вообще компиляторы (точнее, парсеры, как первая стадия компиляции) работают, с полуфилосовской и полупрактической стороны, или о том, как выглядит граматика/парсер конкретно Паскаля. Или вообще имеется в виду связка-мостик между парсером и компилятором, когда мы переходим от анализа к внедрению семантики, описания реального поведения программы.
Кстати, интересует чисто ЛА или всё же синтаксический анализ также?
0
Igor3D
1228 / 595 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
08.06.2013, 20:51 4
Ну Вы уж прямо запугали человека (полу) философской и практической сторонами Во всяком случае практичнее подождать его ответа, а то что все начинается с парсера - это точно
0
08.06.2013, 20:51
OhMyGodSoLong
~ Эврика! ~
1248 / 997 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
09.06.2013, 02:18 5
Цитата Сообщение от Igor3D Посмотреть сообщение
Каждой лексеме присваивается тип (напр s переменная, := операция), ну и дальше это или выполняется (интерпретатор) или строится код (компилятор)
Как нарисовать сову.jpg
0
SysUnit
36 / 33 / 1
Регистрация: 11.01.2013
Сообщений: 370
11.06.2013, 00:41  [ТС] 6
Лексема Тип лексемы
s Идентификатор
:= Знак присваивания
0 Целочисленная константа
for Ключевое слово
i Идентификатор
:= Знак присваивания
0 Целочисленная константа
to Ключевое слово
N Идентификатор
- Знак арифметической операции
1 Целочисленная константа
do Ключевое слово
s Идентификатор
:= Знак присваивания
s Идентификатор
+ Знак арифметической операции
sqr Ключевое слово
( Открывающая скобка
) Закрывающая скобка
a[i] Элемент массива

Если есть ошибки - просьба указать. Если есть уточнения/детали - просьба написать.
0
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,021
Записей в блоге: 22
11.06.2013, 01:16 7
a - Идентификатор
[ - открывающаяся квадратная скобка
i - Идентификатор
] - закрывающаяся квадратная скобка

В таком случае разбор выражения a[i] и a[5] сведётка к одинаковому отношению к a как к идентификатору и к скобочкам также.

P.S. на каком этапе Вы будете определять тип (число, массив, строка) каждого идентификатора?
1
SysUnit
36 / 33 / 1
Регистрация: 11.01.2013
Сообщений: 370
11.06.2013, 10:51  [ТС] 8
Mysterious Light, спасибо!

Цитата Сообщение от Mysterious Light Посмотреть сообщение
P.S. на каком этапе Вы будете определять тип (число, массив, строка) каждого идентификатора?
А на каком лучше/правильнее?
0
Igor3D
1228 / 595 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
11.06.2013, 11:16 9
Выражения в скобках изначально одна лексема, сами скобки (пара) - операция (часто с высшим приоритетом), выполнение ее сводится к вычислению/обработке того что в скобках
0
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,021
Записей в блоге: 22
11.06.2013, 15:40 10
Цитата Сообщение от Igor3D Посмотреть сообщение
Выражения в скобках изначально одна лексема
То есть в строке
Pascal
1
s := a[i*10+j];
i*10+j — это одна лексема?
Спрашиваю, потому что в тонкостях не разбираюсь, но такое утверждение мне кажется достаточно странным.
Igor3D, разберите, пожалуйста, лексически строку
Javascript
1
round(DiffEqSolve(F)(0));
где (описываю смысл, чтоб было понятно, что происходит, на лексический анализ это, естественно, влиять не должно) F — некоторая функция, DiffEqSolve возвращает y(x) — решение y'(x)=F(x), следовательно, вся строка имеет смысл округленного значения y(0). Если то, что в скобках, одна лексема, то Вы предлагаете рассматривать здесь всего три лексемы: round, пару скобок и DiffEqSolve(F)(0)?
0
Igor3D
1228 / 595 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
11.06.2013, 16:21 11
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Igor3D, разберите, пожалуйста, лексически строку
Javascript
1
round(DiffEqSolve(F)(0));
Для простоты полагаем что пишем интерпретатор. Тогда

// шаг 1
round
(DiffEqSolve(F)(0));

Опознали round (известная ф-ция), вычисляем выражение в скобках

// шаг 2
DiffEqSolve
(F)
(0)

Опознали DiffEqSolve (известная ф-ция), вычисляем выражение в скобках

// шаги 3. 4
F
0

Вычисляем значение F, это может быть переменная, ф-ция, константа.

// шаг 5
вычисляем DiffEqSolve (его аргумент вычислен на предыдущем шаге)

// шаг 6
вычисляем значение возвращенное DiffEqSolve (возможно это ф-ция) c аргументом 0

// шаг 7
вычисляем round c вычисленным аргументом

Ну то есть встретив скобки мы выделяем все что в них в одно "выражение" и вычисляем его таким же образом как и исходное. Результат подставляем в исходное и продолжаем вычислять.
0
Evg
Эксперт CАвтор FAQ
20032 / 7600 / 582
Регистрация: 30.03.2009
Сообщений: 21,224
Записей в блоге: 30
11.06.2013, 16:28 12
Пишем свой интерпретатор языка BASIC
См. посты 20 и 29, они касаются твоего вопроса. Но для целостности картины лучше всю тему просмотреть. Там в том числе есть и готовые исходники интерпретатора
0
Igor3D
1228 / 595 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
11.06.2013, 16:55 13
Цитата Сообщение от Evg Посмотреть сообщение
Там в том числе есть и готовые исходники интерпретатора
Лучше пусть сам делает, а то "активно списывающих" и так слишком много
0
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,021
Записей в блоге: 22
11.06.2013, 20:26 14
Цитата Сообщение от Igor3D Посмотреть сообщение
Для простоты полагаем что пишем интерпретатор.
Интерпретация — это не лексический анализ. Это другая задача. Хотя быть только потому, что для интерпретация важна семантика всех конструкций, а для лексического и синтаскического анализа — нет.
Цитата Сообщение от Evg Посмотреть сообщение
Есть две вещи разного уровня: грамматика и лексика. Грамматика - это по сути дела правила построения слов из отдельных букв. Лексика - построение предложений из слов (а последние построены по правилам грамматики)
Это очень интересно.
Далее по тексту Вы анализом текста при заданной грамматикой называете парсинг, а это есть синтаксический анализ (далее СА). Грамматика == Синтаксис?

То есть лексика — это первый этап, когда мы текст бьём на слова. Тогда ЛА нам вообще не нужен, если в тексте заведомо нет ни пробелов, ни слов из более чем 1 буквы (такие языки существуют). Я правильно понимаю?
Когда мы провели ЛА, перед нами последовательность токенов, но мы не знаем, что они означаю и как они образуют предложение. Поэтому (для многих типизированных языков, хотя всё меняется, если есть зарезервированные слова и символы) мы не можем знать тип токена, пока не проведём СА и не построим дерево разбора и не узнаем, какое место занимает конкретный токет, причём одно место — один токен.

Я правильно понимаю, что в этом смысл ЛА: чтоб в узле синтаксического дерева находилась не строка из нескольких символов, а один токен?
offtop
Цитата Сообщение от Igor3D Посмотреть сообщение
Цитата Сообщение от Evg Посмотреть сообщение
Там в том числе есть и готовые исходники интерпретатора
Лучше пусть сам делает, а то "активно списывающих" и так слишком много
это на кого наезд был, на меня или на ТС?
0
OhMyGodSoLong
~ Эврика! ~
1248 / 997 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
11.06.2013, 21:27 15
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Я правильно понимаю, что в этом смысл ЛА: чтоб в узле синтаксического дерева находилась не строка из нескольких символов, а один токен?
Да, чтобы не тащить в грамматику языка правила записи чисел, идентификаторов, выкидывание комментариев, пробелов и прочее. А то синтаксический анализатор сильно от этого усложняется.
0
Igor3D
1228 / 595 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
12.06.2013, 14:00 16
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Интерпретация — это не лексический анализ. Это другая задача. Хотя быть только потому, что для интерпретация важна семантика всех конструкций, а для лексического и синтаскического анализа — нет.
"Семантика", "лексический анализ", "синтаксический" - суть не меняется от используемых слов. Часть того же примера
// шаг 1
round
(DiffEqSolve(F)(0));
Из исходной строки (expression) получен контейнер из 2 элементов. Тип первого "ф-ция", имя ее известно. С ним больше никаких парсингов делать не надо, все уже известно. Тип второго - "выражение в скобках". При этом второй элемент содержит вложенный, пока это подстрока (тип "expression"). На основании приоритета операций решается что надо заняться вложенным expression. В результате он преобразуется в элемент(ы) др типа. Не нравится слово "интерпретатор" - хорошо, тогда мы просто можем наращивать дерево. Напр вместо вычисления вложенного experssion мы заменяем его на вложенный контейнер элементов и.т.д пока все будет так же известно как с элементом "ф-ция round". На этом анализ закончен и нужно приступать к "содержательной части".

Сами по себе "токены" еще ничего не дают - нужно посторить иерархию типированных элементов.
0
Evg
Эксперт CАвтор FAQ
20032 / 7600 / 582
Регистрация: 30.03.2009
Сообщений: 21,224
Записей в блоге: 30
12.06.2013, 21:37 17
Есть три уровня (первые два я часто путаю, какой из них как называется).

1. Грамматика. Правила построения слов из букв. На уровне грамматики описываются правила построения слов (токенов). Т.е. с точки зрения языка паскаль правильными токенами являются: "abc", "123", ":=". Грамматика позволяет из потока букв вырезать слова. Т.е. поток букв "abc:=123" разбивается на три токена
2. Синтаксис. Правило построения предложений из слов. На этом уровне разбирается, что "abc:=123" является правильным синтаксическим предложением, а "123:=abc" - нет.
3. Семантика. Наполнение смыслом предложений. Т.е. запись "a:=b" является синтаксически корректной с точки зрения паскаля. Но если переменные a и b не были описаны, то такая запись ошибочна. Если, например, "a" определена как целочисленная переменная, а "b" - как вещественная, то запись "a:=b" означает не просто присваивание, а приведение типов и только потом присваивание. Всё это называется словом "семантика"

Добавлено через 1 минуту
Словом "парсинг" обычно называют то, что объединяет в себя первый и второй уровень. Это наиболее простые части любого разборщика языка программирования, т.к. эти два уровня легко задаются формальными правилами и имеется целая куча инструментов, которые позволяют автоматизировать грамматический и синтаксический разбор. Но для обучения лучше весь этот разбор писать ручками, не прибегая к инстументам
1
OhMyGodSoLong
~ Эврика! ~
1248 / 997 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
12.06.2013, 22:28 18
4. Прагматика. Как всё то, что понапридумано в семантике, перетащить на реальные вычислительные машины.
0
Igor3D
1228 / 595 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
13.06.2013, 10:20 19
Цитата Сообщение от Evg Посмотреть сообщение
Это наиболее простые ...
легко задаются формальными правилами ...
"Вообще говоря" да, но Вы забыли добавить что легко "для профессионального программиста"

Цитата Сообщение от Evg Посмотреть сообщение
Но для обучения лучше весь этот разбор писать ручками, не прибегая к инстументам
А вот это правильно
0
Evg
Эксперт CАвтор FAQ
20032 / 7600 / 582
Регистрация: 30.03.2009
Сообщений: 21,224
Записей в блоге: 30
13.06.2013, 10:57 20
Цитата Сообщение от Igor3D Посмотреть сообщение
"Вообще говоря" да, но Вы забыли добавить что легко "для профессионального программиста"
Формальные правила, о которых я говорил - это вовсе не программирование, а записанные на бумаге правила. Поскольку они формализованы, то под эти правила уже пишется программа (и вот здесь включается то самое "легко", о котором говорил ты, но не говорил я). А все эти записанные на бумаге правила - они описаны в стандарте языка
0
13.06.2013, 10:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.06.2013, 10:57

Лексический анализатор
Написать программу, которая на основе текста программы на языке Pascal восстанавливает раздел...

Лексический анализатор
Здравствуйте. написать программу, которая выполняет лексический анализ входного текста в...

Лексический анализатор
Здравствуйте. Может быть у кого-нибудь есть код лексического анализатора? Скиньте пожалуйста....


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

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

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