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

Здравствуйте, matros, Вы писали:

M>На выходе синтаксического анализа должно получиться дерево,
M>подскажите какую оно имеет структуру?

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

Здравствуйте, matros, Вы писали:

M>На выходе синтаксического анализа должно получиться дерево,
M>подскажите какую оно имеет структуру?

Структура дерева разбора определяется грамматикой языка (в конечном итоге формирующая синтаксические правила).

Например рассмотрим грамматику G над алфавитом {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, (, ), *, /}

E ::= E + F | F
F ::= F * T | T
T ::= D | (E)
D ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Построим дерево разбора соответствующее грамматике G для входной цепочки 1 + 2 * 5:

+----E----------+
|    |          |
E    |     +----F-----+
|    |     |          |
F    |     F          T
|    |     |          | 
T    |     T          D
|    |     |          |
D    |     D          |

1    +     2    *     5

Как видно из рисунка промежуточные узлы дерева соотвествуют структурным элементам грамматики (нетерминалам), а листы — элементам алфавита (терминальным символам).

Для более детального рассмотрения этого вопроса обращайтесь к специализированной литературе по теории компиляции и перевода (например, http://www.books.ru/shop/books/19047).

Здравствуйте, matros, Вы писали:

M>На выходе синтаксического анализа должно получиться дерево,
M>подскажите какую оно имеет структуру?

Структуру дерева Посмотри документацию к boost::spirit.

Здравствуйте, matros, Вы писали:

M>На выходе синтаксического анализа должно получиться дерево,
M>подскажите какую оно имеет структуру?

Структура обычная. Разного типа узлы содержат подузлы, некоторые константы типа чисел или имен переменных, а также списки из того, что перечислено раньше. Собственно списки самое поганое в таких деревьях, они затрудняют работу с деревом, как с чем-то однородным.

Спасибо, будем разюираться....

Хочу написать, что-то типа командного процессора, для удаленного управления клиентским приложением. т.е. подсовывать его (процессор) в telnet.
Может есть какой-нибудь опыт????

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

Здравствуйте, matros, Вы писали:

M> Хочу написать, что-то типа командного процессора, для удаленного управления клиентским приложением. т.е. подсовывать его (процессор) в telnet.
M>Может есть какой-нибудь опыт????

Я не думаю, что в таком случае у тебя будут очень сложные команды. Тогда разбивай просто на слова. И сделай Escaping.

Тогда вместо дерева у тебя будет просто массив параметров. Как у обычной программы.

Здравствуйте, BUran, Вы писали:

BU>Здравствуйте, matros, Вы писали:

M>> Хочу написать, что-то типа командного процессора, для удаленного управления клиентским приложением. т.е. подсовывать его (процессор) в telnet.
M>>Может есть какой-нибудь опыт????

BU>Я не думаю, что в таком случае у тебя будут очень сложные команды. Тогда разбивай просто на слова. И сделай Escaping.

BU>Тогда вместо дерева у тебя будет просто массив параметров. Как у обычной программы.

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

Определение верности синтаксиса уже имею, а с выходящим деревом разобраться не могу.

M>Охота, что бы были логические операторы, арифметические, возможность построения конвейеров и т.д.
M>просто так было бы не интересно.

M>Определение верности синтаксиса уже имею, а с выходящим деревом разобраться не могу.

Любишь изобретать велосипеды?
Воспользуйся telnet и bash — там все это есть и этим всем ты можешь воспользоваться. Есть исходники.
Ладно, надо свой язык — пользуйся yacc и bison.
Ну или boost::spirit parser.

M>Каким образом оно получаеться т.е. логика его образования, .

Примерная последовательность действий компилятора:
1. Лексический анализ. Получаем по исходному тексту лексическую свёртку. В ней каждой лексеме (значащему слову или символу) соответствует некоторый код. Лексемы могут быть нескольких типов, например: ключевые слова, идентификаторы и знаки операций. В лексической свёртке коды располагаются в том же порядке, что и слова в исходном тексте. Фактически это просто сжатый исходный текст.
Операция выполняется с помощью конечного автомата за линейное время.
2. Синтаксический анализ. На этом этапе из лексической свёртки строят дерево. Для этого нужно иметь грамматику языка. Грамматика содержит терминальные символы, нетерминальные символы и правила. Терминальные символы (терминалы) — это коды из лексической свёртки (для идентификаторов можно использовать его тип). Нетерминальные символы — это символы, отличные от терминальных и вводятся дополнительно. Нетерминал обозначает некоторый тип куска текста, например арифметическое выражение или вызов функции. Среди нетерминалов имеется один выделенный символ (- начальный), обозначающий весь текст.
Терминалы будем обозначать маленькими буквами, а нетерминалы — большими. Начальный символ пусть будет S. Правила пусть будут такие:
S -> a
S -> A+A
A -> a
A -> A*A
Это четыре правила. Они говорят нам, что текст может содержать либо символ 'a' либо сумму призведений 'a'.
Правила описывают все нужные цепочки символов(лексем). С помощью правил можно получать(выводить) такие цепочки. Если лексическая свёртка может быть выведена с помощью правил, то текст является синтаксически правильным.
Выводятся цепочки так. Пишем начальный символ, затем смотрим в каких правилах он записан слева. Берём такое правило на наш выбор и переписываем первую строку с заменой начального символа на то, что записано в правиле справа от стрелочки. Затем выбираем во второй строке любой нетерминал и заменяем его по тому же принципу что и первый. Строка выведена, когда в ней не останется нетерминалов.
Пример вывода:
S
A+A
a+A
a+a
Вывели строку "a+a". Можно вывести и "a*a+a" и "a*a*a+a" и "a*a*a+a*a" и просто "a".
Вывод можно оформить в виде упорядоченного дерева. Вершины — нетерминалы, листы — терминалы. Потомки вершины — символы из правила справа от стрелки в том же порядке.
Для нашего вывода:
S
+-+-+
| | |
A + A
| |
a a
В листах дерева записана лексическая свёртка, в каждом листе один символ(код).

Зачем нужно это дерево?
а. Построив его вы удостоверитесь в синтаксической правильности текста.
б. В дереве раскрывается последовательность выполнения операций, но для этого нужно построить правельную грамматику. Как результат имеем простой способ вычисления выражений. Каждое поддерево является отделной частью и его можно обрабатывать отдельно. Например можно обозначить нетерминалами операции сложения и умножения, сделать такую грамматику, в которой умножения будут потомками сложений и для вычисления значения нужно будет рекурсивно пройтись по дереву.
в. Есть и другое.

Как построить дерево для имеющейся лексической свёртки?
Можно с помощью универсальных средств упомянутых в других сообщениях.
Можно просто написать рекурсивный алгоритм. Для него выписывать правила явно не нужно. Просто идём по свёртке и смотрим какие терминалы нам встречаются, эти терминалы могут содержаться в определённых типах выражений и в определённой последовательности. Тип последовательности часто можно распознать по её началу. Кроме того, зная в каком типе части текста мы находимся мы знаем что может находиться в данном месте и просто перебираем варианты. Например, если мы разбираем приведённую выше граматику, то дойдя до знака плюс мы знаем, что далее должно идти произведение или просто "a".

3. после синтаксического анализа можно провести семантический анализ. Он может включать проверку типов идентификаторов и т.д и т.п.

Все перечисленные шаги можно делать одновременно или отдельно. Во время их проведения можно накапливать дополнительную информацию. Например во время лексического анализа при обнаружении идентификатора его имя заносят в таблицу и присваивают код. Грамматики могут быть и сложнее, в правилах слева от стрелки может быть тоже строка, которую можно заменять, но она должна содержать хотябы один нетерминал. Чем проще граматика, тем может быть проще алгоритм вывода цепочек.
Есть ещё много чего, но об этом лучше почитать.

M>или, может , если делать что-то подобное интерпритатору, то оно вообще не нужно, а нужен ответ "правда-непрада"?

Всё зависит от сложности твоего языка.

Здравствуйте, Аноним, Вы писали:

M>>Каким образом оно получаеться т.е. логика его образования, .

А>Примерная последовательность действий компилятора:
А>1. Лексический анализ. Получаем по исходному тексту лексическую свёртку. В ней каждой лексеме (значащему слову или символу) соответствует некоторый код. Лексемы могут быть нескольких типов, например: ключевые слова, идентификаторы и знаки операций. В лексической свёртке коды располагаются в том же порядке, что и слова в исходном тексте. Фактически это просто сжатый исходный текст.
А>Операция выполняется с помощью конечного автомата за линейное время.
А>2. Синтаксический анализ. На этом этапе из лексической свёртки строят дерево. Для этого нужно иметь грамматику языка. Грамматика содержит терминальные символы, нетерминальные символы и правила. Терминальные символы (терминалы) — это коды из лексической свёртки (для идентификаторов можно использовать его тип). Нетерминальные символы — это символы, отличные от терминальных и вводятся дополнительно. Нетерминал обозначает некоторый тип куска текста, например арифметическое выражение или вызов функции. Среди нетерминалов имеется один выделенный символ (- начальный), обозначающий весь текст.
А>Терминалы будем обозначать маленькими буквами, а нетерминалы — большими. Начальный символ пусть будет S. Правила пусть будут такие:
А>S -> a
А>S -> A+A
А>A -> a
А>A -> A*A
А>Это четыре правила. Они говорят нам, что текст может содержать либо символ 'a' либо сумму призведений 'a'.
А>Правила описывают все нужные цепочки символов(лексем). С помощью правил можно получать(выводить) такие цепочки. Если лексическая свёртка может быть выведена с помощью правил, то текст является синтаксически правильным.
А>Выводятся цепочки так. Пишем начальный символ, затем смотрим в каких правилах он записан слева. Берём такое правило на наш выбор и переписываем первую строку с заменой начального символа на то, что записано в правиле справа от стрелочки. Затем выбираем во второй строке любой нетерминал и заменяем его по тому же принципу что и первый. Строка выведена, когда в ней не останется нетерминалов.
А>Пример вывода:
А>S
А>A+A
А>a+A
А>a+a
А>Вывели строку "a+a". Можно вывести и "a*a+a" и "a*a*a+a" и "a*a*a+a*a" и просто "a".
А>Вывод можно оформить в виде упорядоченного дерева. Вершины — нетерминалы, листы — терминалы. Потомки вершины — символы из правила справа от стрелки в том же порядке.
А>Для нашего вывода:
А> S
А>+-+-+
А>| | |
А>A + A
А>| |
А>a a
А>В листах дерева записана лексическая свёртка, в каждом листе один символ(код).

А>Зачем нужно это дерево?
А>а. Построив его вы удостоверитесь в синтаксической правильности текста.
А>б. В дереве раскрывается последовательность выполнения операций, но для этого нужно построить правельную грамматику. Как результат имеем простой способ вычисления выражений. Каждое поддерево является отделной частью и его можно обрабатывать отдельно. Например можно обозначить нетерминалами операции сложения и умножения, сделать такую грамматику, в которой умножения будут потомками сложений и для вычисления значения нужно будет рекурсивно пройтись по дереву.
А>в. Есть и другое.

А>Как построить дерево для имеющейся лексической свёртки?
А>Можно с помощью универсальных средств упомянутых в других сообщениях.
А>Можно просто написать рекурсивный алгоритм. Для него выписывать правила явно не нужно. Просто идём по свёртке и смотрим какие терминалы нам встречаются, эти терминалы могут содержаться в определённых типах выражений и в определённой последовательности. Тип последовательности часто можно распознать по её началу. Кроме того, зная в каком типе части текста мы находимся мы знаем что может находиться в данном месте и просто перебираем варианты. Например, если мы разбираем приведённую выше граматику, то дойдя до знака плюс мы знаем, что далее должно идти произведение или просто "a".

А>3. после синтаксического анализа можно провести семантический анализ. Он может включать проверку типов идентификаторов и т.д и т.п.

А>Все перечисленные шаги можно делать одновременно или отдельно. Во время их проведения можно накапливать дополнительную информацию. Например во время лексического анализа при обнаружении идентификатора его имя заносят в таблицу и присваивают код. Грамматики могут быть и сложнее, в правилах слева от стрелки может быть тоже строка, которую можно заменять, но она должна содержать хотябы один нетерминал. Чем проще граматика, тем может быть проще алгоритм вывода цепочек.
А>Есть ещё много чего, но об этом лучше почитать.

M>>или, может , если делать что-то подобное интерпритатору, то оно вообще не нужно, а нужен ответ "правда-непрада"?

А>Всё зависит от сложности твоего языка.

РЕСПЕКТ,самое простое изложение материала которое я видел,все бы так писали)))

Здравствуйте, matros, Вы писали:

M>На выходе синтаксического анализа должно получиться дерево,
M>подскажите какую оно имеет структуру?

Дерево может получиться унарным, и выродиться в стек.
Если тебе удастся написать такую грамматику и такой интерпретатор, то очень и очень облегчишь себе жизнь.

Контекстно-свободные грамматики парсятся с помощью стекового автомата.

Его механика, грубо говоря, такая: цепочка лексем последовательно сокращается:

  стек          вход
___/\____    ____/\____
T1 ... Tn ++ L1 ... Loo - частично редуцированная цепочка (T - термы, L - лексемы)
       \__  __/ область редукции (несколько правых термов и несколько левых лексем)
          \/

в результате получается новая цепочка:

T1 ... Tn Tnew ++ L2 ... Loo - лексема превратилась в новый терм
T1 ... Tn' ++ T1 ... Loo - преобразование терма
T1 ... Tn' ++ L2 ... Loo - слияние терма с лексемой, превращение в новый терм
и т.п.

Если задача парсера — построить дерево, то каждый терм — это дерево подвыражения.
Если же задача — интерпретировать выражение, то каждый терм — это результат вычисления подвыражения.

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