Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.216.239.46] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Речь ведётся именно про лексический анализ, т.е. разбиение по токенам.
Ну собственно сабж, допустим на каком-то стейте у нас случилось так, что дальнейшее содержимое подходит под N>1 правил анализа, токен A и некий токен B, как дальше себя вести? Пробовать строить грамматику исходя из каждой из ветвей, а потом смотреть что из этого получилось? Или обычно кидается исключение с сообщенькой, мол, "неопределённое поведение"? Пример: 1) Токен A "class" 2) Токен B "[A-Za-z]+" И текст: class Example На выходе можно получить два "дерева" разбора: 1) A(class) B(Example) 2) B(class) B(Example) Или без грамматики лексический анализ производить невозможно? |
Сообщ.
#2
,
|
|
|
Возможно я ошибаюсь, но похоже ты пытаешься смешать лексический анализ с синтаксическим разбором. В этом случае без грамматики не обойтись. Примеры:
Цитата Serafim @ Или без грамматики лексический анализ производить невозможно? Если в общем - то разные грамматики разбираются по разному. |
Сообщ.
#3
,
|
|
|
Serafim, распространённый и дешёвый принцип: более специализированный токен имеет приоритет перед менее специализированным при прочих равных условиях. У тебя А является частным случаем B, но не всякий B является при этом A. Поэтому A более специализирован, и ему нужно отдать предпочтение.
|
Сообщ.
#4
,
|
|
|
Цитата JoeUser @ Возможно я ошибаюсь, но похоже ты пытаешься смешать лексический анализ с синтаксическим разбором. Ну смотри, в моём представлении есть: 1) Лексер (токенизер): Берёт текст и разбивает его на токены 2) Граммар (синтаксический разбор): Берёт токены, и используя всякие (E)BNF строит AST 3) Семантический разбор: Анализ конечных структур (например, может ли класс А наследоваться от Б, иначе исключение) Я, конечно, набросал на PHP по-быстрому первую часть: https://github.com/SerafimArts/Lexer и полный разбор есть на основе чего-то вроде LL(k): https://goo.gl/jW48ic Но это всё дилетанство, хочется по-нормальному понять как люди делают =))) Yacc я так и не осилил прост. Добавлено Цитата Qraizer @ Serafim, распространённый и дешёвый принцип: более специализированный токен имеет приоритет перед менее специализированным при прочих равных условиях. У тебя А является частным случаем B, но не всякий B является при этом A. Поэтому A более специализирован, и ему нужно отдать предпочтение. В этом случае нужно пилить BNF, иначе не получится понять что есть подмножеством чего =\ Кажется. Или я чего-то не догоняю? Добавлено Ну т.е. реально самый дешёвый вариант - это в порядке приоритета. Объявил раньше, значит и приоритет выше Добавлено Ссылки есть, предложения костылезации есть, так что думаю можно закрывать тему |
Сообщ.
#5
,
|
|
|
Цитата Serafim @ Но это всё дилетанство, хочется по-нормальному понять как люди делают =))) Я выше спецом пару ссылок привел. Прочитай про грамматики. В твоем случае токен "class" зависит от контекста. Пример: class SomeClass { std::string S = " class SomeClass { std::string S = \"\";}"; }; |
Сообщ.
#6
,
|
|
|
Цитата JoeUser @ В твоем случае токен "class" зависит от контекста. Не прокатит, второе включение уже будет внутри строки =) Т.е. другой токен. Плохой пример |
Сообщ.
#7
,
|
|
|
Цитата Serafim @ Не прокатит Ну бегло глянул твое файло на гите - обработки срок я не увидел. Ну а пример не плохой - как раз показывает что отдельно вырванный из контекста идентификатор может быть чем угодно. Строкой, комментарием в коде, текстом HEREDOC, собственно ключевым словом. Поэтому лексический разбор без учета грамматики яп невозможен в общем. |
Сообщ.
#8
,
|
|
|
Serafim
Лексер у меня выделят всего 7 классов: комментарий число слово строка символ-пунктуации(оператор) пробельный символ прочий символ Весь остальной анализ это задача синтаксического анализа. Цитата Serafim @ Или без грамматики лексический анализ производить невозможно? В общем случае лексер нечем не отличается от синтаксического анализа. Но нагляднее разбить на вот такие вот классы и дальше оперировать ими. Конфликты бывают 3-х видов. Свёртка-сдвиг, свёртка-свёртка, сдвиг-сдвиг. Так как основная проблема конфликтов присуще только математическим-формулам. То выход простой приоритеты операторов. Помимо приоритетов операторов операторы ещё делятся на леворекурсивные и праворекурсивные. Всё это описывается в грамматике. Помимо этого ещё есть ряд способов борьбы с конфликтами http://www.opennet.ru/docs/RUS/bison_yacc/bison_8.html#SEC87 Цитата Serafim @ Объявил раньше, значит и приоритет выше Можно и так. Цитата Serafim @ Пробовать строить грамматику исходя из каждой из ветвей, а потом смотреть что из этого получилось? Строить всмысле вычислять? А почему-бы и нет? Это называется рекурсивный анализ с возвратами либо многопроходным анализом. Правда его мало кто применяет. |
Сообщ.
#9
,
|
|
|
Цитата Serafim @ Пример: 1) Токен A "class" 2) Токен B "[A-Za-z]+" Пример неудачный. Или, наоборот, очень удачный. Если возникла неоднозначность, то один из токенов (в данном случае А) скорее всего является подмножеством другого (токена В в данном случае). И лексему следует ставить в соответствие более "узкому" токену. |
Сообщ.
#10
,
|
|
|
А каким образом можно определить какой токен "уже"? Ну, например, в случае грамматики а-ля ANTLR:
A : 'class' ; B : [A-Za-z]+ ; |
Сообщ.
#11
,
|
|
|
Цитата Serafim @ каким образом можно определить какой токен "уже"? А это при создании токенов надо думать. В данном случае токен 'class' соответствует шаблону токена '[A-Za-z]+' - он соответственно "уже". Первый токен должен получить больший приоритет, а второй - меньший. Если имеется соответствие токену с более высоким приоритетом, любые соответствия токену с меньшим - игнорируются. Хуже, если мы, скажем, имеем лексему 'abc' и токены '[a-z][a-z]c' и 'a[a-z][a-z]', они пересекаются, но не вложены, и лексема соответствует обоим. Тут приоритет должен задаваться при разработке, и даже может быть динамическим... но в любом случае "остаться должен только один". |
Сообщ.
#12
,
|
|
|
Цитата JoeUser @ обработки срок я не увидел. Ну так регулярка будет такой: "[^"\\]+(\\.[^"\\]*)*" Добавлено Цитата Akina @ А это при создании токенов надо думать. В данном случае токен 'class' соответствует шаблону токена '[A-Za-z]+' - он соответственно "уже". Первый токен должен получить больший приоритет, а второй - меньший. Если имеется соответствие токену с более высоким приоритетом, любые соответствия токену с меньшим - игнорируются. Хуже, если мы, скажем, имеем лексему 'abc' и токены '[a-z][a-z]c' и 'a[a-z][a-z]', они пересекаются, но не вложены, и лексема соответствует обоим. Тут приоритет должен задаваться при разработке, и даже может быть динамическим... Хм, кажется, что это как раз решается на уровне приоритететов во время объявления. Описывая грамматику - стоит описать вначале частные случаи, а потом уже общие. Цитата Akina @ но в любом случае "остаться должен только один". Вот это всё же я не понимаю и, раз уже определились, что токенизация без синтаксического анализа бессмысленна, то, кажется, что всё же имеет смысл делать несколько "деревьев" Например: T_BRACE_OPEN: '{'; T_BRACE_CLOSE: '}'; T_CLASS: 'class'; T_KEYWORD: [A-Za-z]+; ClassExpr: <T_CLASS> <T_KEYWORD> <T_BRACE_OPEN> <ТУТ ТЕЛО КАКОЕ-ТО> <T_BRACE_CLOSE> И код для разбора: class Example {} Получим на определённом шаге 2 "дерева": // 1 T_CLASS T_KEYWORD T_BRACE_OPEN T_BRACE_CLOSE // 2 T_KEYWORD T_KEYWORD T_BRACE_OPEN T_BRACE_CLOSE Но только первый вариант можно "свернуть" в "ClassExpr". По-этому приоритет тут не важен. Разве нет? P.S. Учитывая то, что я ещё не просматривал ссылки выше с мануалами по алгоритмам, есть подозрения, что вопрос глупый, т.к. данный алгоритм соответствует какому-то одному. |
Сообщ.
#13
,
|
|
|
Цитата 1) Токен A "class" 2) Токен B "[A-Za-z]+" Я, возможно, скажу ересь, но по-моему указанная проблема не относится к лексическому анализу. С точки зрения лексики "class" - это и есть частный случай "[A-Za-z]+". Разделение слов на просто слова и слова ключевые должно происходить уровнем чуть выше. В принципе, можно лексеру дать список ключевых слов, и пусть он ищет полученное слово в этом списке и принимает решение. Но лучше возложить эту задачу на парсер. Тогда можно будет использовать текущий контекст: если ожидается, к примеру, имя поля, то "class" - это просто слово, если же ничего такого не ожидается, то "class" - это слово ключевое. (Конечно, не обязательно использовать именно такую логику, "вы просто могли бы"). P. S. Лексический анализ - дело очень простое, можно легко написать лексер под конкретный парсер. Городить универсальный лексер под чужим копирайтом - зачем? |
Сообщ.
#14
,
|
|
|
Цитата AVA12 @ огда можно будет использовать текущий контекст: если ожидается, к примеру, имя поля, то "class" - это просто слово, если же ничего такого не ожидается, то "class" - это слово ключевое. Вот с этим, кстати, сложнее. Т.к. в моём случае понять чем что является можно только уже после построения AST. Получается, что в качестве имени поля приходится перечислять все токены, включая зарезервированные кейворды. Цитата AVA12 @ P. S. Лексический анализ - дело очень простое, можно легко написать лексер под конкретный парсер. Городить универсальный лексер под чужим копирайтом - зачем? Я же писал где-то выше, что всё это уже есть (ссыль выше есть), но реализация довольно примитивная, отсюда и попытки копнуть глубже и понять на пальцах какие есть способы, как лучше, и прочие шняги =))) |
Сообщ.
#15
,
|
|
|
Цитата Serafim @ Вот это всё же я не понимаю и, раз уже определились, что токенизация без синтаксического анализа бессмысленна, то, кажется, что всё же имеет смысл делать несколько "деревьев" Чего? Все нормальные люди знают что токенезация, вернее легализация это разделения на слова. Как разделение на слова могут зависит от их порядка? *** ! Прошу воздержаться от таких форм высказываний Цитата Serafim @ Т.к. в моём случае понять чем что является можно только уже после построения AST В русском языке есть слова? А в английском есть слова? Даже в математике есть слова и в Паскале есть слова и в Форте есть слова. И в Японском тоже есть слова, хотя и без пробелов.- во всех языках есть слова. Так вот понять где какая лексема очень легко и AST тут совсем лишнее. |