Темыч, Зенитчик и все остальные Help!!!

[SLIM]

Так как я очень плохо воспринимаю абстрактые данные прошу помощи показать на практике (по-шагово если можно на реальной грамматике)
1. Устранение неоднозначностей грамматики. Для примера возьмем грамматику
exp-->exp op exp
exp-->id
op-->+
op-->*

Задача переделать такую грамматику на однозначную. Зная при этом возможность неоднозначности разбора предложения id+id*id.
В итоге получаем два дерева разбора....ну ту я думаю ясно

2.Принцип устранения левой рекурсии, но вот здесь мне бы интересно увидеть реальную грамматику (ну более менее реальную)
Здесь есть пара подпунктов
2.1. Устранение непосредственной левой рекурсии, например при грамматике
S-->Sa
2.2.Устранение рекурсии при выводе за два и более шага
S-->Aa|b
A--Ac|Sd|e
когда получаем вывод
S=>Aa=>Sda

Теория то есть, но вот не могу понять как это в реале происходит

[Ramzes]

SLIM, где твоя совесть? пятница! вечер! Только позитифф

[SLIM]

SLIM, где твоя совесть? пятница! вечер! Только позитифф

Так я че я ниче....я так..побаловаться

З.Ы. С отлучкой Хакера и редкими приходами Рэя и незахода Гайдара с редкими встречами Алибека тут развелось нереально много флууудддааа
Ну да ладно. Мож кто че по теме скажет

[Ramzes]

а где флуд? флуд мы в миг прекратим, если он в тематических разделах

[SLIM]

а где флуд? флуд мы в миг прекратим, если он в тематических разделах

Отмазался....мы тут за два дня ( и я в том числе) зафлудили две темы...нереальный парадокс - зафлудить темы нетематического раздела - нонсонс.
Но тем не менее...кто-то тут про смену профессии говорил а мы туда фотки свои стали выкладывать, я тут про синтаксический анализ, а ты ту про пазитифко....

Вот мы все гады (ну ладно,накинешся щас...только я гад)

UPD
Мама, сообщение за номером 666...пипец, что-то будет

[Viper]

Мама, сообщение за номером 666...пипец, что-то будет

Ну че будет, че будет, забаним!

[tyomitch]

1. Букварный пример же.
exp-->exp + exp
exp-->term
term-->term * term
term-->id

2.1. очевидно, S-->aS

2.2. Эквивалентное определение: A-->Ac|Aad|bd|e
а теперь
A1-->cA1|adA1|
A-->bdA1|eA1

[SLIM]

1. Букварный пример же.
exp-->exp + exp
exp-->term
term-->term * term
term-->id

Ты меня не понял, по какому правилу это делается, вот что я хотел узнать

2.1. очевидно, S-->aS

Это очень не очевидно.
Например как ты поступишь при
E-->E+T|T

Ну и опять таки какое правило то

[tyomitch]

1. Для каждого приоритета создаётся новый нетерминал.
2. Очевидно, E-->T+E|T
Ну видно же, что язык T(+T)* равен (T+)*T

[SLIM]

ммм, таки да....теперь понял

[Хакер]

SLIM, нафиг ты залез сюда, мой способ задания правил разбора круче

P.S. Выходи в mail.ru-агент.

[tyomitch]

Так поделись же своим мега-способом с общественностью!

[Хакер]

НУ, идею я уже раскрыл, хотя изначально не хотел.
А реализацию (т.е. dll-шки с функциями) --- боюсь что общественность в ней не разберётся без доки, а доку я писать не буду.

[tyomitch]

Так твоя идея распознаёт только регулярные языки?
Слабовато.

[Хакер]

Моя идея универсальна. Она ничего не знает о тех данных, которые она распознаёт (будь то исполняемый код или скрипт на PHP), и в принципе может обрабатывать всё, что угодно.

Это DFA. На базе DFA построен и декомпилятор x86-кода, и мега-быстрый словарь и парсер.

Над DFA построен TKN, упрощающий построение обработчика для текстовых типов данных (парсеров для xml, ini, языков программирования и т.п.).

[tyomitch]

Что такое TKN, я не знаю, но при помощи DFA ты даже правильность расстановки скобок не проверишь, не то чтобы распознавать ЯП.

[Хакер]

Правильность расстановкее скобок я при помощи DFA проверю (с чего ты взял, что не проверю? ). Правда не на этапе токенизации, а на этапе обработки токенизированных данных.

[tyomitch]

О чём и речь
Настоящие грамматики затем и нужны, чтобы "обработка токенизированных данных" тоже шла автоматически.
У тебя, в случае разбора текстовых языков, очень маленькая разница между входным потоком байтов и выходным потоком токенов; в чём же выигрыш?

[Хакер]

Что значит "тоже шла автоматически"? Она и у меня идёт автоматически (а не вручную). Или ты имеешь в виду, что классический парсер схавает в качестве входящих данных описание грамматики и сам код, и на выходе сразу же даст готовое дерево? Т.е. одним махом, за один этап, а не за несколько, как у меня?

[tyomitch]

За несколько, как у тебя.
Но дерево построится по описанию грамматики само, без рукотворного кода.
А у тебя откуда берётся разборщик второго этапа? Пишешь руками впридачу к описанию языка?

[Хакер]

Что значит без рукотворного кода? Анализатор описания грамматики сам по себе зарождается?

А TokenSequence можно обработать руками, можно скормить куда-то, можно превратить в дерево используя тот же DFA.

[tyomitch]

Что значит без рукотворного кода? Анализатор описания грамматики сам по себе зарождается?

Анализатор описания грамматики (произвольной) != анализатор потока токенов для конкретной грамматики

А TokenSequence можно обработать руками, можно скормить куда-то, можно превратить в дерево используя тот же DFA.

Вот не сделаешь ты дерево из DFA, говорю же.
Я всё это учил и сдавал

[Хакер]

Анализатор описания грамматики (произвольной) != анализатор потока токенов для конкретной грамматики

(Никто и не спорил) Но он же не зарождается сам собой, его же всё равно нужно написать (в данном случае писать его придётся SLIM-у).

Вот не сделаешь ты дерево из DFA, говорю же.

Ну обоснуй это заявление.
DFA — не более чем технология построения программы в рантайме. Можно вообще всю программу сделать через DFA. При таком раскладе, программная структура, созданная с помощью DFA, в принципе, может сделать то же самое, что и обычный код. Почему, при этом, ты заявляешь, что программа, построенная с помощью DFA чего-то не может — мне непонятно.

Я всё это учил и сдавал

Ты учил и сдавал классику, но не то, что придумал я. Ты пытаешься смотреть на мой принцип разбора через призму классики, но этого делать нельзя.

[tyomitch]

Вот не сделаешь ты дерево из DFA, говорю же.

Ну обоснуй это заявление.
DFA — не более чем технология построения программы в рантайме. Можно вообще всю программу сделать через DFA.
...

Я всё это учил и сдавал

Ты учил и сдавал классику, но не то, что придумал я. Ты пытаешься смотреть на мой принцип разбора через призму классики, но этого делать нельзя.

Если ты в классическое понятие "DFA" вместо классического смысла вкладываешь какой-то свой, тогда -- да, конечно.
Не важно.

Построй мне дерево для языка правильных расстановок скобок (т.е. в алфавите только два символа "()")
Тогда наверное пойму, что ты имеешь в виду.

[Хакер]

DFA --- не классическое понятие, а библиотека, функции которые имеют префикс "Dfa" и отвечают за построение того, что я описал в топике "Second hand (Хакерское abandonware)".
А ты думал это Determinated Finite Automat?

Про дерево не понял.

[tyomitch]

DFA --- не классическое понятие, а библиотека, функции которые имеют префикс "Dfa" и отвечают за построение того, что я описал в топике "Second hand (Хакерское abandonware)".

Обвёл меня вокруг пальца!
Теперь тебе ещё надо написать библиотеку с префиксом VB6, для полной неразберихи.

А ты думал это Determinated Finite Automat?

Deterministic Finite Automaton
(урок правописания)

Про дерево не понял.

Вход: строка. Выход: либо дерево (в любом виде), либо ошибка (если в строке есть нескобки, или скобки расставлены неправильно).

[Хакер]

Хочу хороший пример входных данных и выходного дерева.

[tyomitch]

Код: Выделить всё

()((()(()))(())())
1 234 56   78  9

   0
  / \
1   2
    /|\
   3 9 7
  / \   \
4   5   8
     |
     6


[SLIM]

Хакер, мы все видели только описание супербыстрого поиска по словарю
Никто не видел основной идеи той самой разработки, но ИМХО она действительно идет в разрез с классическими понятиями.
Поэтому нужно друг другу объяснить свои идеи, а уж потом спорить...
У темыча есть своя доля правды...
Задача любого синтаксического анализатора состоит в нескольких вещах
1. Принять поток данных и определить относится ли он к данному языку и грамматике (больше грамматики конечно)
2. Обработав все это нужно вывести дерево разбора, или ошибку в разборе если таковая имеется.

Деревья разбора строятся по-разному, и тут все очень друг на друге завязано.

Просто я к чему все это. Грамматика описывает некую структуру в целом а не по отдельности. Понятие токен без грамматики то же самое что и атом - самостоятельно они бесполезны. Поэтому скармливать любой поток данных - где-то да не сработает.

Ну а если задаться заданием структуры грамматики, тут вступает уже придуманные учеными методы. Я если честно сам пытался, но в итоге все стекается к уже придуманному...Т.е. задавать грамматику именно так как это делал например я в первом топике. Разбирать...вот тут самые большие проблемы. Для того чтобы разборщик работал быстрее и оптимизируют правила разбора и т.д.

Я бы поставил тебе памятник если бы была такая ситуация
1. Получаем строку неизвестно чего
2. Находим в нем структуру
3. В следующий раз при получении строки такой же структуры уже не переструктурируем, а используем старую структуру
4. При возникновении неправильности первой изночальной структуру, переструктурируем ее по-новой

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

[Хакер]

Задача любого синтаксического анализатора состоит в нескольких вещах
1. Принять поток данных и определить относится ли он к данному языку и грамматике (больше грамматики конечно)
2. Обработав все это нужно вывести дерево разбора, или ошибку в разборе если таковая имеется.

Вообще говоря, нельзя так громко кричать "нужно". "Нужно" у каждого своё. Мне, например, может оказаться, что дерево разбора и не нужно.

То, что действительно нужно, это данные одного вида (который менее удобен для оперирования ими), перевести в данные другого вида (более удобного).

Каким будет этот "другой вид" — будет ли это дерево, связанный список или массив зависит от тебя и твоей задачи. Так что заявлять, что какой-то там анализатор должен код превратить всенепременно в дерево, — неправильно. Можно конечно насильно заставлять себя делать именно так, как кто-то сделал кто-то раньше. Но ты же не называешь свои функции foo и bar?

Понятие токен без грамматики то же самое что и атом - самостоятельно они бесполезны.

Здравсьте.
У меня имеется реализованный не до конца CodeBox (текст бокс для отображения кода со всеми соотв. фукнциями). Этот кодебокс используется TOKENSEQUENCE для отрисовки и для подсветки синтаксиса. Вот наглядный пример того, чем полезен поэтапный подход. Если я пишу просьенький текстовый редактор с подсветкой синтаксиса, то мне хватит токенайзера. Если я пишу не просто текстовый редактор, а среду разработки с компилятором, то я подвергну токенизированные данные следующей обработке с помощью DFA-автомата. Сначала последовательность символов превратилась в последовательность токенов, а в этот раз последовательность токенов превратится в какую-то другую последовательность. Сколько будет таких этапов и что в конечном счёте получится зависит от меня, от моей фантазии и моей задачи.

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

Чем хорошо программирование — здесь можно крутиться и придумывать свои методы. Я изначально отвернулся от методов, придуманных учёными и с тех пор ни разу не пожалел.

Я бы поставил тебе памятник если бы была такая ситуация
1. Получаем строку неизвестно чего
2. Находим в нем структуру
3. В следующий раз при получении строки такой же структуры уже не переструктурируем, а используем старую структуру
4. При возникновении неправильности первой изночальной структуру, переструктурируем ее по-новой

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

Это глупость. Т.е. это невозможная в принципе вещь, даже если реализующий будет неимоверно умён. Что же касается естественных языков: "косил косой косой косой". Последнии три слова одинаковые, но тем не менее, одно из них обозначает зайца, другое инструмент, а третье является прилагальнрым. Которое — какое, не ответишь даже ты, не то что программа.