На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишите свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Решение конфликтов в лексическом анализе
Речь ведётся именно про лексический анализ, т.е. разбиение по токенам.

Ну собственно сабж, допустим на каком-то стейте у нас случилось так, что дальнейшее содержимое подходит под N>1 правил анализа, токен A и некий токен B, как дальше себя вести? Пробовать строить грамматику исходя из каждой из ветвей, а потом смотреть что из этого получилось? Или обычно кидается исключение с сообщенькой, мол, "неопределённое поведение"?

Пример:
1) Токен A "class"
2) Токен B "[A-Za-z]+"

И текст:
ExpandedWrap disabled
    class Example


На выходе можно получить два "дерева" разбора:
1) A(class) B(Example)
2) B(class) B(Example)

Или без грамматики лексический анализ производить невозможно?
user posted image
Возможно я ошибаюсь, но похоже ты пытаешься смешать лексический анализ с синтаксическим разбором. В этом случае без грамматики не обойтись. Примеры:
  • Разбор обратной польской записи - для данной грамматики неоднозначности быть не может, если только не ошибка (например тернарная операция с пустым стеком)
  • "С++" ... знаки "<" или ">" трактуются от контекста, без грамматики никак (почитать)
Цитата Serafim @
Или без грамматики лексический анализ производить невозможно?

Если в общем - то разные грамматики разбираются по разному.
Мои программные ништякиhttp://majestio.info
Serafim, распространённый и дешёвый принцип: более специализированный токен имеет приоритет перед менее специализированным при прочих равных условиях. У тебя А является частным случаем B, но не всякий B является при этом A. Поэтому A более специализирован, и ему нужно отдать предпочтение.
Сообщение отредактировано: Qraizer -
Одни с годами умнеют, другие становятся старше.
Цитата 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, иначе не получится понять что есть подмножеством чего =\ Кажется. Или я чего-то не догоняю? :huh:

Добавлено
Ну т.е. реально самый дешёвый вариант - это в порядке приоритета. Объявил раньше, значит и приоритет выше :lol:

Добавлено
Ссылки есть, предложения костылезации есть, так что думаю можно закрывать тему :good:
user posted image
Цитата Serafim @
Но это всё дилетанство, хочется по-нормальному понять как люди делают =)))

Я выше спецом пару ссылок привел. Прочитай про грамматики.

В твоем случае токен "class" зависит от контекста. Пример:
ExpandedWrap disabled
    class SomeClass {
      std::string S = " class SomeClass { std::string S = \"\";}";
    };
Мои программные ништякиhttp://majestio.info
Цитата JoeUser @
В твоем случае токен "class" зависит от контекста.

Не прокатит, второе включение уже будет внутри строки =) Т.е. другой токен. Плохой пример
user posted image
Цитата Serafim @
Не прокатит

Ну бегло глянул твое файло на гите - обработки срок я не увидел.
Ну а пример не плохой - как раз показывает что отдельно вырванный из контекста идентификатор может быть чем угодно. Строкой, комментарием в коде, текстом HEREDOC, собственно ключевым словом. Поэтому лексический разбор без учета грамматики яп невозможен в общем.
Мои программные ништякиhttp://majestio.info
Serafim
Лексер у меня выделят всего 7 классов:
комментарий
число
слово
строка
символ-пунктуации(оператор)
пробельный символ
прочий символ

Весь остальной анализ это задача синтаксического анализа.

Цитата Serafim @
Или без грамматики лексический анализ производить невозможно?

В общем случае лексер нечем не отличается от синтаксического анализа. Но нагляднее разбить на вот такие вот классы и дальше оперировать ими.
Так что будем считать, что у лексера таких проблем не возникает. Приоритет лексемы определяет их порядок следования в грамматике. А вот у синтаксического анализатора там свои решения.

Конфликты бывают 3-х видов. Свёртка-сдвиг, свёртка-свёртка, сдвиг-сдвиг.
Так как основная проблема конфликтов присуще только математическим-формулам. То выход простой приоритеты операторов. Помимо приоритетов операторов операторы ещё делятся на леворекурсивные и праворекурсивные. Всё это описывается в грамматике.

Помимо этого ещё есть ряд способов борьбы с конфликтами
http://www.opennet.ru/docs/RUS/bison_yacc/bison_8.html#SEC87

Цитата Serafim @
Объявил раньше, значит и приоритет выше

Можно и так.


Цитата Serafim @
Пробовать строить грамматику исходя из каждой из ветвей, а потом смотреть что из этого получилось?

Строить всмысле вычислять? А почему-бы и нет? Это называется рекурсивный анализ с возвратами либо многопроходным анализом.
Правда его мало кто применяет.
Сообщение отредактировано: Pavia -
Правильный обед должен состоять из 5 блюд приготовленных из 33 ингредиентов.
Цитата Serafim @
Пример:
1) Токен A "class"
2) Токен B "[A-Za-z]+"

Пример неудачный. Или, наоборот, очень удачный. Если возникла неоднозначность, то один из токенов (в данном случае А) скорее всего является подмножеством другого (токена В в данном случае). И лексему следует ставить в соответствие более "узкому" токену.
Сообщение отредактировано: Akina -
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
А каким образом можно определить какой токен "уже"? Ну, например, в случае грамматики а-ля ANTLR:
ExpandedWrap disabled
    A
        : 'class'
        ;
     
    B
        : [A-Za-z]+
        ;
Сообщение отредактировано: Serafim -
user posted image
Цитата Serafim @
каким образом можно определить какой токен "уже"?

А это при создании токенов надо думать. В данном случае токен 'class' соответствует шаблону токена '[A-Za-z]+' - он соответственно "уже". Первый токен должен получить больший приоритет, а второй - меньший. Если имеется соответствие токену с более высоким приоритетом, любые соответствия токену с меньшим - игнорируются.
Хуже, если мы, скажем, имеем лексему 'abc' и токены '[a-z][a-z]c' и 'a[a-z][a-z]', они пересекаются, но не вложены, и лексема соответствует обоим. Тут приоритет должен задаваться при разработке, и даже может быть динамическим... но в любом случае "остаться должен только один".
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
Цитата JoeUser @
обработки срок я не увидел.

Ну так регулярка будет такой:
ExpandedWrap disabled
    "[^"\\]+(\\.[^"\\]*)*"


Добавлено
Цитата Akina @
А это при создании токенов надо думать. В данном случае токен 'class' соответствует шаблону токена '[A-Za-z]+' - он соответственно "уже". Первый токен должен получить больший приоритет, а второй - меньший. Если имеется соответствие токену с более высоким приоритетом, любые соответствия токену с меньшим - игнорируются.
Хуже, если мы, скажем, имеем лексему 'abc' и токены '[a-z][a-z]c' и 'a[a-z][a-z]', они пересекаются, но не вложены, и лексема соответствует обоим. Тут приоритет должен задаваться при разработке, и даже может быть динамическим...

Хм, кажется, что это как раз решается на уровне приоритететов во время объявления. Описывая грамматику - стоит описать вначале частные случаи, а потом уже общие.

Цитата Akina @
но в любом случае "остаться должен только один".

Вот это всё же я не понимаю и, раз уже определились, что токенизация без синтаксического анализа бессмысленна, то, кажется, что всё же имеет смысл делать несколько "деревьев"

Например:
ExpandedWrap disabled
    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>


И код для разбора:
ExpandedWrap disabled
    class Example {}


Получим на определённом шаге 2 "дерева":
ExpandedWrap disabled
    // 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. Учитывая то, что я ещё не просматривал ссылки выше с мануалами по алгоритмам, есть подозрения, что вопрос глупый,
т.к. данный алгоритм соответствует какому-то одному. :rolleyes:
user posted image
Цитата
1) Токен A "class"
2) Токен B "[A-Za-z]+"

Я, возможно, скажу ересь, но по-моему указанная проблема не относится к лексическому анализу. С точки зрения лексики "class" - это и есть частный случай "[A-Za-z]+". Разделение слов на просто слова и слова ключевые должно происходить уровнем чуть выше. В принципе, можно лексеру дать список ключевых слов, и пусть он ищет полученное слово в этом списке и принимает решение. Но лучше возложить эту задачу на парсер. Тогда можно будет использовать текущий контекст: если ожидается, к примеру, имя поля, то "class" - это просто слово, если же ничего такого не ожидается, то "class" - это слово ключевое. (Конечно, не обязательно использовать именно такую логику, "вы просто могли бы").

P. S. Лексический анализ - дело очень простое, можно легко написать лексер под конкретный парсер. Городить универсальный лексер под чужим копирайтом - зачем?
Цитата AVA12 @
огда можно будет использовать текущий контекст: если ожидается, к примеру, имя поля, то "class" - это просто слово, если же ничего такого не ожидается, то "class" - это слово ключевое.

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

Цитата AVA12 @
P. S. Лексический анализ - дело очень простое, можно легко написать лексер под конкретный парсер. Городить универсальный лексер под чужим копирайтом - зачем?

Я же писал где-то выше, что всё это уже есть (ссыль выше есть), но реализация довольно примитивная, отсюда и попытки копнуть глубже и понять на пальцах какие есть способы, как лучше, и прочие шняги =)))
user posted image
Цитата Serafim @
Вот это всё же я не понимаю и, раз уже определились, что токенизация без синтаксического анализа бессмысленна, то, кажется, что всё же имеет смысл делать несколько "деревьев"

Чего? Все нормальные люди знают что токенезация, вернее легализация это разделения на слова. Как разделение на слова могут зависит от их порядка? ***
!
Прошу воздержаться от таких форм высказываний


Цитата Serafim @
Т.к. в моём случае понять чем что является можно только уже после построения AST

В русском языке есть слова? А в английском есть слова? Даже в математике есть слова и в Паскале есть слова и в Форте есть слова. И в Японском тоже есть слова, хотя и без пробелов.- во всех языках есть слова.
Так вот понять где какая лексема очень легко и AST тут совсем лишнее.
Сообщение отредактировано: JoeUser -
Правильный обед должен состоять из 5 блюд приготовленных из 33 ингредиентов.
1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
0 пользователей:


Рейтинг@Mail.ru
[ Script Execution time: 0,1689 ]   [ 19 queries used ]   [ Generated: 20.11.17, 22:44 GMT ]