Форум программистов, компьютерный форум, киберфорум
Теория и практика программирования
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
175 / 17 / 1
Регистрация: 13.02.2016
Сообщений: 14
1

Синтаксический разбор языков программирования

06.08.2016, 18:32. Просмотров 2150. Ответов 6
Метки нет (Все метки)


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

Но ввиду отсутствия образования, не могу вникнуть в суть ГРАММАТИК СИНТАКСИЧЕСКОГО РАЗБОРА.
То есть суть почти понимаю и могу решать простые задачи и упражнения по разбору (чисто их правилами разбора), но очень в отрыве от любого кода или даже просто алгоритма. Программирую на бейсике.
Книги конечно читаю, но там всё объяснение в формулах и всё как-то не однозначно.
Очень хотелось бы получить ответы от знающих людей на несколько вопросов по этой теме, что-бы было от чего отталкиватся.

1) Насколько я понял LL(1) грамматика самая простая и быстрая, это так -?
Простая всмысле ручного программирования, и парсер будет самый эффективный по скорости разбора -?

2) Является ли EcmaScript (JavaScript) языком подходящим для LL(1) грамматики -? или только LR грамматики -?

3) ТЕРМИНАЛЫ это - "for", "next", "else", то есть конкретные однозначные имена операторов, переменных и тд. НЕТЕРМИНАЛЫ это - формулы, выражения, конструкции, то есть не конкретный оператор с именем "FOR", а просто абстактно любой "оператор" Я правильно понял -?

4) Из википедии: Синтаксический LL-анализатор (LL parser) — в информатике нисходящий синтаксический анализатор для подмножества контекстно-свободных грамматик. Он анализирует входной поток слева направо, и строит левый вывод грамматики.

Низходящий - я понял, анализирует поток слева на право - это начиная с первой буквы до конца текста или опять какая-то абстракция с подставами правил - ?
Как понять левый вывод грамматики - на примере каком нибудь -? хоть на яблоках .

Если не трудно, подскажите пж-ста, конкретные однозначные ответы, задолбали эти абстракции.
СПАСИБО.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.08.2016, 18:32
Ответы с готовыми решениями:

Теория языков программирования
Всех приветствую. Пожалуйста, порекомендуйте книги или ресурсы на которых можно почитать о...

Запоминание разных языков программирования
Приветствую. Только начал изучать C++, до этого изучал VB.Net. В связи с этим возник вопрос:...

Описание языков программирования + фреймворки
Задача: нужно быстро получить общее представление о том, на чем сейчас программирует народ. ...

Последовательность изучения языков программирования
Добрый день! Я начала изучение программирования с абсолютного 0, и начала все это дело с js....

6
175 / 17 / 1
Регистрация: 13.02.2016
Сообщений: 14
10.08.2016, 12:24  [ТС] 2
Здравствуйте. Жаль ни кто подсказать не может.
У меня за неделю неожиданно продвинулись познания, поэтому отвечу сам себе

1) Да
2) с ECMASCRIPT точно справится "Грамматики с операторным предшествованием"
3) Да с оговорками
4) Анализирует поток слева на право - это начиная с первой буквы до конца текста.

Виной всему эта книга : Конспективное изложение теории языков часть 1, 2015г
Есть ещё часть 2, практическая.

Написано по доходчивей, чем обычно пишут в такой литературе.
Вот пример объяснения грамматики:

Рассмотрим грамматику, которая описывает синтаксическую конструкцию «объявление переменной» в стиле языка Си:
G12a({t, d, «;» , «,»}, {S,A},{
(1) S→ t «;»
(2) A→ d | (3) A «,»d
},S).
В этой грамматике:
(1), (2), (3) - номер применяемого правила.
- символ «t» обозначает произвольный тип переменной;
- символ «d» обозначает произвольный идентификатор;
- символы «;» и «,» обозначают сами себя. Символы заключены в кавычки, чтобы отличить их от соответствующих знаков пунктуации.
- символ «S» является целевым и обозначает оператор объявления, то есть всю конструкцию оператора.
- символ «A» обозначает список объявляемых переменных.
Правило (1) S→ tA«;» имеет следующий смысл:
Строка объявления – это тип, список переменных, точка с запятой.
Правило (2) A→ d: список переменных – это идентификатор
Правило (3) A→ A «,»d : список переменных – это список переменных, запятая, идентификатор
С помощью этой грамматики порождаются цепочки вида:
«тип ид;»
«тип ид, ид;»
«тип ид, ид, ид;» и т.д.
Здесь «тип» обозначает произвольный тип t (тип объявляемой переменной), а «ид», соответственно- некоторый произвольный идентификатор d (имя переменной).
Грамматика порождает цепочку «тип ид;» следующим образом:
S → (1) tA; →(2) td;
Цепочка вида «тип ид, ид;»
Преобразовывается так:
S → (1) tA; → (3) tA,d; → (2) td,d;.

Моё !!! Описание смысла этого преобразования :
Оператор объявления переменных (S) содержит : тип переменных(t), список переменных(A), точка с запятой(
Далее, если при чтении текста программы выясняется, что переменная в списке не одна, то применяем правило (3) и распиливаем список переменных (A) на список переменных(A)+ запятая(,)+ имя переменной(d)), то есть выдёргиваем переменную(d) и запятую из списка(A) и пишем их рядом. И так пока в списке(A) не останется только одна переменная (d).

Если в списке остаётся только одна переменная, то применяем правило (2), то есть полностью заменяем (оставшийся) список переменных(A) на имя последней переменной(d), а символ (A) полностью исключаем из формулы.


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

Спасибо себе, дальше я сам
0
175 / 17 / 1
Регистрация: 13.02.2016
Сообщений: 14
11.08.2016, 14:25  [ТС] 3
Всем привет!
Кому интересна тема " компиляторы, интерпретаторы, трансляторы, синтаксический разбор языков программирования, грамматики разбора и подобное ".

Вот подборка литературы (РУС) на данную темы.

ссылка удалена

Вот перечень файлов в архиве:

Вирт - Разработка ОС и компилятора. 2012 с исходниками
31-Конечный-автомат
instruction_tables - таблица времени выполнения инструкций ассемблера
LL(k)-ГРАММАТИКИ И ТРАНСЛЯЦИИ
Абельсон Х. Структура и интерпретация компьютерных программ.2004
Автоматное программирование
Алгоритмы оптимизации кода
Алгоритмы, языки, автоматы и компиляторы
Ахо - Компиляторы - Принципы, Технологии, Инструменты 2003
Ахо, - Компиляторы. Принципы, технологии, инструменты.2ed.2008
Баранов язык ФОРТ и его реализации 1988
Вирт Н. - Построение компиляторов (Классика программирования) - 2010
Виртуальные машины компиляция
Восходящие анализаторы
Генератор синтаксических анализов для КС грамматик 2010
Гриффитс А.GCC. Настольная книга. Диасофт.[RUS,624p,2004]
Гуренко В.В. Введение в теорию автоматов
Давайте создадим компилятор
ИНТЕРПРЕТАТОР СКРИПТОВОГО ЯЗЫКАJAVASCRIPT
Интерпретация Лиспа
Карпов - Основы построения трансляторов (2005)
Конечные автоматы. Разбор выражений
Конспективное изложение теории языков 2015
Конструирование компиляторов (учебное пособие) 2015
Креншоу Д. Пишем компилятор
Лекции Грамматики слабого предшествования
Лекции о компиляции
ЛЕКЦИИ ПО ТЕОРИИ АЛГОРИТМОВ 2009
Лекции по транслятору
ЛЕКЦИЯ № 3 ТЕОРИЯ ЯЗЫКОВ И ФОРМАЛЬНЫХ ГРАММАТИК
Лингвистическое обеспечение а. систем
МАГАЗИННЫЕ АВТОМАТЫ ГЛАВА 5
МЕТОДЫ ТРАНСЛЯЦИИ конспект лекций ч1
Методы трансляции уч. пособие 2000
Методы ускорения алгоритмов распознавания символов
Недетерминированные конечные автоматы 2007
Недетерминированные конечные автоматы
О некоторых свойствах автоматов с магазинной памятью
Опалёва. Языки программирования и методы трансляции (2005)
Основы разработки трансляторов в САПР
Основы трансляции конспект лекций
Основы функционального программирования 2004
Парсер-комбинаторы и левая рекурсия
Построение простейшего дерева вывода
Практикум по теории языков и трансляции 2015
Приведение грамматики к виду LL(1)
Принципы построения распознавателей КС-языков без возвратов
Программа управления компиляцией GNU make Версия 3.79
Проект «исследовательский компилятор»
Разбор и вычисление выражений
Редкая профессия
Робин Хантер - основные концепции компиляторов 2002
Свердлов Языки программирования и методы трансляции 2007
Серебряков В.А. - Основы конструирования компиляторов - 2001
Способы внутреннего представления программ
Сравнение алгоритмов восходящих и нисходящих.
Теорема о равносильных определениях LL(1)
Теория автоматов 2001
Теория и практика языков программирования 2013
Теория и реализация языков программирования 2006
Теория синтаксического анализа, перевода и компиляции 1978
Теория синтаксического анализа, перевода и компиляции. 1978 Том 2
Теория языков программирования и методы трансляции
Технологии трансляции 2008
Трансляторы.chm
Фомичев - Формальные языки
Формальные грамматики и языки 1999
Формальные языки и основы трансляторов 2003
Элементы теории конечных автоматов 2010
Языки и трансляции 2008
Языки программирования и методы трансляции 2007
Языки программирования и методы трансляции 2013 конспект
Языки программирования и методы трансляции ч2
Языки программирования и методы трансляции
ЯЗЫКИ ПРОГРАММИРОВАНИЯ концепции и принципы 1986
Курс о теории формальных языков
Курс Основы построения трансляторов
Папка со статейками из инета

Пользуйтесь на здоровье!
0
175 / 17 / 1
Регистрация: 13.02.2016
Сообщений: 14
12.08.2016, 16:12  [ТС] 4
Уточнение по поводу терминальных - нетерминальных символов. Что бы не было вопросов.

Лексический анализ текста - это разбор символов входного текста (из букв и цифр) на лексемы.
Лексема – простейшая смысловая конструкция распознаваемого языка,
может состоять из нескольких символов (знаков, букв, цифр), например это может быть
ключевое слово («FOR» , «NEXT» и т.д.») или идентификаторы («A» -имя переменной)
или знаки пунктуации («,» «.» «:» «;» и т.д.) или знаки математических операций («+» «-» «*» «/» и т.д.)
или литералы («123» - непосредственная запись значения: символьная, числовая или строковая)

Лексема определённой категории – токен.

После лексического анализа образуется поток токенов- лексем, который является входным текстом для синтаксического анализа, а токены – ТЕРМИНАЛЬНЫМИ символами для синтаксических грамматик разбора.

Нетерминальные символы – это условные символы, обозначающие КОНСТРУКЦИИ языка, состоящие из токенов, а не отдельные токены. Например: IF – токен, THEN – токен, ELSE – токен, а условный символ «А», обозначающий синтаксическую конструкцию «IF then Else» - это и есть НЕТЕРМИНАЛЬНЫЙ символ «А».

А в основном, смысл грамматик разбора в подмене по ОПРЕДЕЛЁННЫМ ПРАВИЛАМ нетерминалов "А" на терминалы "а" - они же токены.
Всё просто.

Есть много нюансов - читайте книги!
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
13.08.2016, 10:21 5
sergey2400
Я так понимаю, что вы хотите написать язык программирования.
Я тоже пытался раньше это сделать. После сильного упрощения
этой задачи, удалось лишь написать интерпретатор арифметического
выражения (а также компилятор). А вот от написания интерпретатора
логического выражения я отказался. Взамен решил написать
десятичный ассемблер.... нет, одному человеку тут не справиться.
Так, что теперь отошел от этого дела и занялся другими программами.
0
175 / 17 / 1
Регистрация: 13.02.2016
Сообщений: 14
13.08.2016, 10:52  [ТС] 6
Браузер собрался делать... который будет работать по моим правилам, то есть НЕТ рекламе, все всплывающие (модальные) окна обязательно с возможностью закрытия и тд.

На движках собственного изготовления JavaScript, HTML, рендер через OpenGl.
Года через 2 начну, сейчас изучаю технологии.
0
175 / 17 / 1
Регистрация: 13.02.2016
Сообщений: 14
30.01.2017, 04:02  [ТС] 7
Ха! Синтаксический анализ движка V8 работает методом рекурсивного спуска!!!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.01.2017, 04:02

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Как делаются диалекты языков программирования?
Как делаются диалекты языков программирования? Прошу расписать полный путь (допустим у нас взят...

А какой из языков программирования сейчас актуален
если учитывать дальнейшее развитие IT сферы? Просто я хочу начинать изучать програмирование, но не...

Подскажите с каких языков программирования начать
Здравствуйте, мне 17, поступил на 1 курс на факультет компьютерных систем. Пока что у нас нет...

Вопрос об эффективности приминения языков программирования.
Чё то я на свои вопросы не могу получить ответа. Как то всё медленно. В реале разговор продолжился...


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

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

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