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

VNN>По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — фактически только одни определения типов. Хотел бы посоветововаться с коллегами — насколько эта задача сложна?

Урвень курсовой на 3-4 курсе института.

VNN> Руководство крайне недовольно, что ковыряюсь уже 3-й месяц и по моим планам выходит еще 2 с половиной.

Да, что то многовато.

VNN>Пришлось самостоятельно описывать грамматику языка, пробовал воспрльзоватсья какимими то существующими наработками типа YACC и LEX, но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям.

Это была твоя главная ошибка.

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

VNN>По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — фактически только одни определения типов. Хотел бы посоветововаться с коллегами — насколько эта задача сложна? Руководство крайне недовольно, что ковыряюсь уже 3-й месяц и по моим планам выходит еще 2 с половиной.

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

VNN>Пришлось самостоятельно описывать грамматику языка, пробовал воспрльзоватсья какимими то существующими наработками типа YACC и LEX, но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям. Ща ковыряю синтаксический анализ, процесс идет тяжко.

Вот это совсем плохо. Существующими наработками стоит воспользоваться. Хотя бы вот из каких соображений. Даже если пишут парсер вручную (если по к-л причинам не удаётся воспользоваться yacc), вначале записывают грамматику в BNF, а потом делают всю "чёрную" работу (там даже не надо думать, только шпарить по имеющемуся алгоритму генератора LL-парсера). Так какая разница: записать грамматику неформально, или на языке, используемом yacc?

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

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

SH>Не веришь — потрать неделю на antlr. Или на bison. Хотя можно и yacc-ом пользоваться. Короче, на любой один из них.

Я бы все таки советовал начать с LL парсеров, т.е. c antlr или CoCo/R

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

VNN>Вот, опять. КАК "использовать"-то? Можно в 3-4-х пунктах описать как оно ваще работает?

Ну ты бы почитал документацию что ли. Туториалы какие-нибудь, и всё стало бы ясно.

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

if a > b then return a else return b

Превращается во что-то, что можно изобразить так:

[IF, IDENTIFIER("a"), GT, IDENTIFIER("b"), THEN, RETURN, IDENTIFIER("a"), ELSE, RETURN, IDENTIFIER("b")]

Это автоматизируется lex'ом. Каждый класс лексем можно описать регулярным выражением. При этом рядом с каждым регулярным выражением ставится семантическое правило, т.е. тот код, который выполняется, когда находится лексема нужного класса. Например (в терминах ocamllex):

let letter = ['a'-'z' 'A'-'Z']
rule token = parse
    letter+ as name         { IDENTIFIER(name) }
  | "if"                    { IF }
  | "then"                  { THEN }
  | "return"                { RETURN }
  | "else"                  { ELSE }
  | "while"                 { WHILE }
  | "do"                    { DO }
  | "begin"                 { BEGIN }
  | "end"                   { END }
  | "<"                     { LT }
  | ">"                     { GT }
  | "="                     { EQ }
  | ":="                    { COLONEQ }
  | "+"                     { PLUS }
  | ";"                     { SEMICOLON }
  и т.д.

В случае с C как правило заводят две глобальные переменные — одна хранит класс лексемы, другая (типа union) какую-либо вспомогательную информацию, например, значение числа или название идентификатора. Соотв, семантические правила в большинстве случаев просто присваивают нужные значения этим переменным. Но всех тонкостей самого lex я не помню.

Далее, поток лексем передаётся синтаксическому анализатору, который выдаёт AST (abstract syntactic tree — абстрактное синтаксическое дерево). Преобразование исх. текста в AST — и есть конечная цель работы парсера. Этот этап автоматизируется yacc. Чтобы описать синтаксис языка, регулярных выражений не хватает. Тут уже нужны так называемые контекстно-зависимые грамматики (а то и что-то более мощное), одним из возможных способов описания которых является BNF, в терминах которого как правило и описывается язык в документации.

К сожалению, yacc не поддерживает BNF, и грамматику ему надо задавать практически в том же виде, как определено в математике. Некоторые другие генераторы парсеров так или иначе понимают BNF. Однако, как мне показалось (не смотрел всю спецификацию), синтаксис OIL описан именно в виде, понимаемым яками.

Вот пример (ocamlyacc):

operator:
    IF expr THEN operator ELSE operator    { Ast.If_op($2, $4, Some $6) }
  | IF expr THEN operator                  { Ast.If_op($2, $4, None) }
  | IDENTIFIER COLONEQ expr                { Ast.Assign_op($1, $3) }
  | RETURN expr                            { Ast.Return_op $2 }
  | WHILE expr DO operator                 { Ast.While_op($2, $4) }
  | BEGIN operators END                    { Ast.Multiple_op $2 }
  | и т.д.
;

expr:
    expr LT expr                           { Ast.Binary_expr(Ast.Less_sym, $1, $3) }
  | expr GT expr                           { Ast.Binary_expr(Ast.Greater_sym, $1, $3) }
  | expr EQ expr                           { Ast.Binary_expr(Ast.Less_sym, $1, $3) }
  | expr PLUS expr                         { Ast.Binary_expr(Ast.Sum_sym, $1, $3) }
  | expr STAR expr                         { Ast.Binary_expr(Ast.Prod_sym, $1, $3) }
  | ID                                     { Ast.Id_expr $1 }
  | и т.д.
;

operators:
    operator                               { [$1] }
  | operator SEMICOLON operators           { $1 :: $3 }
;

Здесь в фигурных скобках опять стоят семантические правила. $1, $2, ... — это переменные, указывающие на значения соотвествующих символов. Например, если разбирается строка

if a > b then return a else return b

и при этом парсер уже понял, что a > b — это expr, return a — operator, return b — operator, то вся строка будет подходить под правило:

IF expr THEN operator ELSE operator

Тогда $2 будет равно разобранному значению "a > b", т.е. Ast.Binary_expr(Ast.Greater_sym, Ast.Id_expr "a", Ast.Id_expr "b"). Соответсвенно, $4 и $6 в этом случае означают результаты разбора "return a" и "return b".

В yacc для C опять же, для записи результатов используется спец. глобальная переменная. Семантические правила в этом случае просто меняют значение этой переменной.

Надо заметить вот ещё что. Пусть есть строка:

a + b > c * d

В этом случае yacc не знает, как разбирать выражение — либо по правилу:

expr PLUS expr

где $1 = 'a', $3 = 'b > c * d', либо

expr GT expr

где $1 = 'a + b", $3 = 'c * d', либо

expr STAR expr

где $1 = 'a + b > c", $3 = 'd'. Чтобы парсер мог правильно распарсить такое выражение, надо задать приоритет символов PLUS, GT, STAR, либо вручную исключить конфликты из грамматики (но это не для начального освоения). Как задаются приоритет и ассоциативность, опять же написано в документации по yacc.

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

VNN>К сожалению, у меня не только небыло опыта написания подобных вещей, но и даже про теорию я не особо знал. Сейчас что-то поверхам похватал. Я до сих пор внятно не представляю КАК собствено использовать всевозможные Яки, Бизоны и прочих "копытных" в моем проекте. Как мне тут уже подсказали, нужно описать все BNF-выражения языка (они уже есть) сначала в виде своих классов, потом в виде некого кода Яка и прочих, а вот последующие шаги в тумане.

Дракона уже начал читать?
Попробую объяснить по другому. Генераторы парсеров, как тут уже справедливо заметили, порождают два куска кода. Кусок №1, принимая на вход некий поток сырых данных (в случае текстового языка это как правило поток символов) на выходе выдает поток лексем — минимальных частей языка. Как правило в качестве лексем фигурируют ключевые слова, операторы, знаки препинания, константы. К примеру, выражение 1+2*3 будет преобразовано в поток {константа1, оператор +, константа 2, оператор *, константа 3}. Как правило лексемы описываются регулярными грамматиками(это очень узкий класс простых грамматик), часто бывает, что внешний код умеет переключать режимы лексера, это позволяет делать ключевые слова, являющеиеся таковыми только в определенном контексте.
Т.е., упрощенно, лексер это такая функция, на входе которой текст,а на выходе набор примитивов, которые в этом тексте выявлены. Генератор может на основе регулярных выражений построить тебе такую функцию. А можешь ее реализовать самостоятельно — это, как правило, довольно несложно.
Как только мы получили поток лексем, нам необходимо этот поток проанализировать и выявить в нем структуру. Вот структура как раз и описывается ввиде BNF-правил. Генератор, пользуясь этими правилами, строит код, который эти правила выявляет, либо определяет факт того, что текст под эти правила не подходит. Алгоритмов наложения правил на поток лексем много, но для языков программирования наиболее часто используются http://en.wikipedia.org/wiki/LR_parser и LL алгоритмы. Подробности изучишь сам, здесь е замечу, что LL парсер значительно проще, но несколько медленнее и способен анализировать более узкий класс грамматик.
Но просто проанализировать недостаточно. Нужно еще эти результаты зафиксировать. Практически всегда для этого используют т.н. AST — абстрактное синтаксическое дерево, т.е. древовидная структура (часто немодифицируемая), описывающая выражения и конструкции языка программирования. В случае приведенного примера выражения обычно получится что то такое:

оператор +
    константа 1
    оператор *
        константа 2
        константа 3

В большинстве случаев за тебя никто это дерево не построит и ты должен будешь строит его самостоятельно на целевом языке программирования ввиде кусочков кода, привязанных к правилам грамматик. Т.е. код, написанный в правиле с оператором * вызовется, если таковой оператор будет обнаружен и корректно (с точки зрения грамматики) использован, и ты в этом коде должен будешь создать экземпляр узла "оператор", передав в качестве параметров тип оператора (*) и уже построенное AST обоих его операндов.
На следующем этапе, если язык это подразумевает, производится разрешение типов, т.е. в соответствие идентификаторам ставится некая информация, которая описывает что это за идентификатор — ссылка на тип в AST, ссылка на тип во внешней библиотеке, ссылка на объявление использованной переменной, параметра или поля и т.д. В примере с калькулятором это может быть связывание имени функции в выражении с описанием, какая у нее должна быть реализация.
Наконец, на последнем этапе ты должен по типизированному дереву построить либо код на другом языке (транслятор), либо исполняемый код (компилятор), либо просто начать исполнять программу (интерпретатор). В приведенном примере, если мы преобразуем его в IL, то получим примерно следующее:

ldc.i4 1
ldc.i4 2
ldc.i4 3
mul.ovf
add.ovf
ret

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

K>Если же нужен статический контроль типов, составление всяческих таблиц, графов и т.п., то может потребоваться масса времени.
Ну вопщем да, типы данных имеют место быть. Собсно вот описание языка OIL.

K>Вот это совсем плохо. Существующими наработками стоит воспользоваться. Хотя бы вот из каких соображений.
Плохо то, что у меня действительно нет теоретических знаний в компиляторах, да и программироваие как таковое в институте изучалось слабо (в силу специальности) и давно. Для большинства задач пока вполне хватало самообразования, но вот тут явно орешек достался не по зубам :-(

K>вначале записывают грамматику в BNF, а потом делают всю "чёрную" работу (там даже не надо думать, только шпарить по имеющемуся алгоритму генератора LL-парсера).
Собсно, в вышепреведенном PDF-файле сам OIL так уже описан, честно говоря, это сильно не помогло. Мне нужно не просто прочитать (проверить синтаксическую верность) программу на OIL, а создать ее модель в памяти для последующего "визуального программирования", мне показалось, что в данном случае yacc мне совсем не помощник. Вот на следующем этапе когда нужно будет транслировать OIL в стандартый Си, тут наверное готовые анализаторы и кодогенераторы помогут. Я прав?

ЗЫ
Блин, дочего же тяжко себя ощущать по пояс деревянным :-(

VadNuNik wrote:
>
> Здравствуйте, hexis, Вы писали:
>
> H>Что касается lex и yacc — я бы сказал, что отказываться от них можно,
> H>но, как правило — нежелательно, и нужно точно знать на что идешь, и,
> H>главное — почему lex/yacc не устраивают.
> Я не врубился как при помощи этих тулов получить модель в памяти. Один
> же черт нужно будет получать такое представление для визуального
> отображения и редактирования.

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

Выглядит примерно так:
Берем исходную грамматику в BNF:

<enumeration> ::=
    "[" <enumerator_list> "]"
<enumerator_list> ::=
    <enumerator>
    | <enumerator_list> "," <enumerator>
<enumerator> ::=
    <name> <description>
    | <name> <impl_parameter_list> <description>

Создаем классы для преставления перечисления в памяти:

#define optional /* optional */

struct Enumerator
{
    Enumerator(char * _name,
        optional ImplParameterList * _plist,
        optional char * _description)
    : name(_name), plist(_plist), description(_description)
    {
    }

    char * name;
    optional ImplParameterList * plist;
    optional char * description;
};

struct Enum
{
    Enum(Enumerator * e)
    {
        add_enumerator(e);
    }

    void add_enumerator(Enumerator* e)
    {
        enumerators.push_back(e);
    }

    std::list<Enumerator*> enumerators;
};

и связываем все это в yacc

%union
{
    Enum       _enum;
    Enumerator _enumerator;
};

%type <_enum>        enumeration enumerator_list
%type <_enumerator>     enumerator
%type <string>        string description

%%
enumeration: '[' enumerator_list ']'
        { $$ = $2; }
    ;

enumerator_list : enumerator
        { $$ = new Enum($1); }
    | enumerator_list ',' enumerator
        { $1->add_enumerator($3); $$ = $1; }
    ;

enumerator: name description
        { $$ = new Enumerator($1, NULL, $2); }
    | name impl_parameter_list description
        { $$ = new Enumerator($1, $2, $2); }
    ;

description:
    /* empty definition */    { $$ = NULL; }
    | ':' string        { $$ = $2; }
    ;

Как видите, чем ближе промежуточное представление к исходной грамматике
— тем проще его получить. Единственное, с чем есть сложности — это то,
что yacc не позволяет использовать наследуемые атрибуты. Если они нужны,
что придется взять или LL (antlr, coco/R, LLgen) или расширение yacc (на
вскидку имена не помню, но если надо — покопаюсь в архивах), или
обойтись — просто получится чуть сложнее.

>
> H>Так-что, если хотите — еще не поздно этим заняться.
> Я хочу реализовать эту систему и желательно уложиться в срок
>
> Тут уже не раз помянали некого "красного дракона", пардон за невежество,
> это что? Гугл все больше какой-то фильм подсовывает.

Это книга Ахо, Сети, Ульман "Компиляторы: принципы, технологии,
инструменты". Там на обложке дракон нарисован.

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

VNN>Пишу на С++ за еду Парсеры и компиляторы никогда не писал, даже во время учебы — не входило в скудный курс программирования (АСУ).

Тогда восаользуйся Бизоном.

VD>>Мой тебе совет. Выбери построитель парсеров наиболее подхдящий для языка реализации и используй его.
VNN>Вот, опять. КАК "использовать"-то? Можно в 3-4-х пунктах описать как оно ваще работает?

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

Могу только в общих чертах описать то что тебе нужно узнать.
1. Следует изучить BNF (см. Википедию).
2. Следует освоить метод парсинга рекурсивным спуском. В общем-то, для твоей задачи его за глаза хватит. Тогда можно и без построителей парсеров обойтись.
3. Желательно своить построитель парсеров (Бизон в твоем случае будет, пожалуй, оптимальным выбором). Можно попытаться использовать Spirit из boost — это построитель парсеров реализованный в рамках С++ средствами метапрограммирования на шаблонах. Минусы Спирита: замедляет компиляцию проекта, порождает слишком большие бинарники и (особенно) промежуточные файлы (под несколько гиг для весьма скромной грамматики), имеет плохие диагностические сообщения (так как шаблоны С++ не предоставляют средств для выдачи оных). Зато не прийдется искать генераторы кода. Все есть в рамках буста.

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

ЗЫ

Откровенно говоря делать свои языки — это не благодарная задача.

SH>>Не веришь — потрать неделю на antlr. Или на bison. Хотя можно и yacc-ом пользоваться. Короче, на любой один из них.

AVK>Я бы все таки советовал начать с LL парсеров, т.е. c antlr или CoCo/R

если у него там язык "похож на Си" (хоть и "проще") ("пока"), то LL ему не поможет да и вообще.. мало что поможет

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

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

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

F>>Вы, к сожалению, не написали на каком языке пишете свой анализатор языка. Тогда было бы проще посоветовать где глянуть существующие реализации.
VNN>Да, вот как раз сейчас и занят проектированием системы классов для синтаксического разбора. Вообще у меня уже какой-то зверинец из паралелльных иерархий получается — описание грамматики и сущностей (в виде XML — мне так было проще), соответсвенно система проверки файла описания языка (подразумевается, что язык может модифицироваться под конкретный случай), иераррхия описания документа, иерархия синтаксического анализатора, семантическая иерархия... Песец, голова пухнет, первый раз такое. Ощущение напоминает момент когда после 10летнего перерыва занялся программированием и втыкался в ООП, но тогда дедлайн не маячил вот так близко
Ох уж эти классы Да еще "системы классов" Ей-богу, не понимаю: зачем усложнять то, что прекрасно делается на самом обыкновенном и надежном С. Поищите хотя бы "книгу дракона" и просмотрите первые главы. Пусть вы потратите пару недель на это, но зато поймете что ничего сверхзаумного там нет. Вы же сами писали, что анализируете С-подобный язык. А примеров реализаций языков такого типа — вагон. Можно глянуть к примеру здесь. Человек собрал довольно неплохую коллекцию свободнх компиляторов/интерпретаторов.

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

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

H>>Что касается lex и yacc — я бы сказал, что отказываться от них можно,
H>>но, как правило — нежелательно, и нужно точно знать на что идешь, и,
H>>главное — почему lex/yacc не устраивают.
VNN>Я не врубился как при помощи этих тулов получить модель в памяти. Один же черт нужно будет получать такое представление для визуального отображения и редактирования.

H>>Так-что, если хотите — еще не поздно этим заняться.
VNN>Я хочу реализовать эту систему и желательно уложиться в срок

VNN>Тут уже не раз помянали некого "красного дракона", пардон за невежество, это что? Гугл все больше какой-то фильм подсовывает.
Не "красный дракон", а "книга дракона":
Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003

По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — фактически только одни определения типов. Хотел бы посоветововаться с коллегами — насколько эта задача сложна? Руководство крайне недовольно, что ковыряюсь уже 3-й месяц и по моим планам выходит еще 2 с половиной.
Пришлось самостоятельно описывать грамматику языка, пробовал воспрльзоватсья какимими то существующими наработками типа YACC и LEX, но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям. Ща ковыряю синтаксический анализ, процесс идет тяжко. Это действительно такая тривиальная задача и выпускник ВУЗа по специальности "программирование" нынче пишет свой компилятор за 2 дня?!!!

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

VNN>По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — фактически только одни определения типов. Хотел бы посоветововаться с коллегами — насколько эта задача сложна? Руководство крайне недовольно, что ковыряюсь уже 3-й месяц и по моим планам выходит еще 2 с половиной.

Я свой язык программирования никогда не писал, и сейчас оценил бы это месяцев в 6 на создание интерпретатора простого С-подобного языка (в объем работ включается компилятор исходника в байткод и виртуальная машина для его исполнения).

VNN>Пришлось самостоятельно описывать грамматику языка, пробовал воспрльзоватсья какимими то существующими наработками типа YACC и LEX, но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям.

Это вряд ли — задачу лексического и синтаксического анализа в большинстве случаев эти инструменты (или подобные им) решают лучше всего — как в плане "качества кода", так и в скорости разработки.

VNN>Ща ковыряю синтаксический анализ, процесс идет тяжко. Это действительно такая тривиальная задача и выпускник ВУЗа по специальности "программирование" нынче пишет свой компилятор за 2 дня?!!!

Я бы вообще не стал писать свой интерпретатор/компилятор — есть большое количество готовых, достаточно выбрать наиболее подходящий и подонать под специфические требования. Это намного проще, чем писать свой с нуля.

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

VNN>Пришлось самостоятельно описывать грамматику языка, пробовал воспрльзоватсья какимими то существующими наработками типа YACC и LEX, но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям.

Напрасно. Месяц на разбирательство (максимум) + месяц на язык (опять максимум).
Даже если сейчас выкинуть все твои наработки, выйдет быстрее. Точнее, выйдет ещё быстрее, т.к. с учётом опыта тебе не понадобится месяц на въёзжание.

Не веришь — потрать неделю на antlr. Или на bison. Хотя можно и yacc-ом пользоваться. Короче, на любой один из них. Неделя при твоих сроках не так критична, а сэкономить может много.

VNN>Ща ковыряю синтаксический анализ, процесс идет тяжко. Это действительно такая тривиальная задача и выпускник ВУЗа по специальности "программирование" нынче пишет свой компилятор за 2 дня?!!!

Зависит. От выпускника, от языка, от задач стоящих перед компилятором. Синтаксический анализ и парсинг действительно хорошо автоматизируются, а вот с генерацией кода и/или интерпретацией — сложнее. В среднем — нет, конечно.

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

AVK>Я бы все таки советовал начать с LL парсеров, т.е. c antlr или CoCo/R

Хм, мне было проще пользоваться bison, чем antlr.

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

VNN>По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — фактически только одни определения типов. Хотел бы посоветововаться с коллегами — насколько эта задача сложна? Руководство крайне недовольно, что ковыряюсь уже 3-й месяц и по моим планам выходит еще 2 с половиной.
VNN>Пришлось самостоятельно описывать грамматику языка, пробовал воспрльзоватсья какимими то существующими наработками типа YACC и LEX, но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям. Ща ковыряю синтаксический анализ, процесс идет тяжко. Это действительно такая тривиальная задача и выпускник ВУЗа по специальности "программирование" нынче пишет свой компилятор за 2 дня?!!!

Ну, лексический анализатор пишется за вечер Я в свое время написал, до сих пор им пользуюсь в разных проектах. Без LEX, естественно.
С синаксическим сложнее, особенно для си-подобных языков. Но если подумать, то можно обойтись безо всяких YACC. Я недавно создавал компилятор для некоего гибрида basic и c, вполне рабочий, умеет находить ошибки во всей программе, а не останавливаться на первой попавшейся. По сути — метод рекурсивного спуска. А вообще в этих задачах главное — не сам анализатор, а очень грамотно продуманная система классов для хранения всех структур.

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

VNN>По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — фактически только одни определения типов. Хотел бы посоветововаться с коллегами — насколько эта задача сложна? Руководство крайне недовольно, что ковыряюсь уже 3-й месяц и по моим планам выходит еще 2 с половиной.
VNN>Пришлось самостоятельно описывать грамматику языка, пробовал воспрльзоватсья какимими то существующими наработками типа YACC и LEX, но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям. Ща ковыряю синтаксический анализ, процесс идет тяжко. Это действительно такая тривиальная задача и выпускник ВУЗа по специальности "программирование" нынче пишет свой компилятор за 2 дня?!!!
Вы, к сожалению, не написали на каком языке пишете свой анализатор языка. Тогда было бы проще посоветовать где глянуть существующие реализации. Вот, к примеру, подборка реализаций языков программирования на Java:
здесь.

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

F>Вы, к сожалению, не написали на каком языке пишете свой анализатор языка. Тогда было бы проще посоветовать где глянуть существующие реализации.
Да, вот как раз сейчас и занят проектированием системы классов для синтаксического разбора. Вообще у меня уже какой-то зверинец из паралелльных иерархий получается — описание грамматики и сущностей (в виде XML — мне так было проще), соответсвенно система проверки файла описания языка (подразумевается, что язык может модифицироваться под конкретный случай), иераррхия описания документа, иерархия синтаксического анализатора, семантическая иерархия... Песец, голова пухнет, первый раз такое. Ощущение напоминает момент когда после 10летнего перерыва занялся программированием и втыкался в ООП, но тогда дедлайн не маячил вот так близко :-(

VadNuNik wrote:
>
> По работе пишу парсер/синтаксический/семантический анализатор языка.
> Внешне похож на С, но сильно проще (пока) — фактически только одни
> определения типов. Хотел бы посоветововаться с коллегами — насколько эта
> задача сложна? Руководство крайне недовольно, что ковыряюсь уже 3-й
> месяц и по моим планам выходит еще 2 с половиной.
> Пришлось самостоятельно описывать грамматику языка, пробовал
> воспрльзоватсья какимими то существующими наработками типа YACC и LEX,
> но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям.
> Ща ковыряю синтаксический анализ, процесс идет тяжко. Это действительно
> такая тривиальная задача и выпускник ВУЗа по специальности
> "программирование" нынче пишет свой компилятор за 2 дня?!!!

Из опыта. Достаточно простой с-подобный язык: спецификация языка,
разработка компилятора в байт код, виртуальной машины и библиотеки
поддержки — 3 месяца. При этом в компиляторе реализована полная
инфраструктура — AST, гибкая поддержка типов (наподобие ML), разного
рода оптимизации, подключение различных backend-ов и т.д.

Что касается lex и yacc — я бы сказал, что отказываться от них можно,
но, как правило — нежелательно, и нужно точно знать на что идешь, и,
главное — почему lex/yacc не устраивают. Вобще задача синтаксического и
лексического анализа не самая сложная часть компиляции, и, как правило,
нет смысла на ней заостряться. Если говорить о сложности изучения lex и
yacc, то (опять же из опыта), очное обучение человека, незнакомого с
этой областью вообще, занимает минимальное количество времени —
буквально пару-тройку дней. Тем более, что с грамматиками все так или
иначе знакомы, нужно только пояснить отдельные принципы самого yacc,
LALR анализа и дать набор базовых решений типовых ситуаций.

Так-что, если хотите — еще не поздно этим заняться.

VadNuNik wrote:
> K>вначале записывают грамматику в BNF, а потом делают всю "чёрную"
> работу (там даже не надо думать, только шпарить по имеющемуся алгоритму
> генератора LL-парсера).
> Собсно, в вышепреведенном PDF-файле сам OIL так уже описан, честно
> говоря, это сильно не помогло. Мне нужно не просто прочитать (проверить
> синтаксическую верность) программу на OIL, а создать ее модель в памяти
> для последующего "визуального программирования", мне показалось, что в
> данном случае yacc мне совсем не помощник. Вот на следующем этапе когда
> нужно будет транслировать OIL в стандартый Си, тут наверное готовые
> анализаторы и кодогенераторы помогут. Я прав?

Не, lex/yacc тут — самое то. их основная задача — помочь структурировать
вход, а именно такая задача перед вами и стоит. И еще не поздно
переключиться — по приведенной грамматике действительно можно очень
быстро написать анализатор, строящий отражение структуры в памяти. а
затем и добавить компиляцию.

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

H>Что касается lex и yacc — я бы сказал, что отказываться от них можно,
H>но, как правило — нежелательно, и нужно точно знать на что идешь, и,
H>главное — почему lex/yacc не устраивают.
Я не врубился как при помощи этих тулов получить модель в памяти. Один же черт нужно будет получать такое представление для визуального отображения и редактирования.

H>Так-что, если хотите — еще не поздно этим заняться.
Я хочу реализовать эту систему и желательно уложиться в срок :-)

Тут уже не раз помянали некого "красного дракона", пардон за невежество, это что? :-) Гугл все больше какой-то фильм подсовывает.

VNN>По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — VNN>фактически только одни определения типов.

Если только декларация типов — то где-то максимум две недели. Что с генератором парсеров, что вручную.
Берешь готовый пример для соответствующего или похожего синтаксиса и вперед.

Вообще по описанию, очень похоже на какой-нибудь IDL или Slice. И для того и для другого полно парсеров — бери любой, допиливай (отпиливай лишнее) и готово. Ну и вообще готовых решений, которые используют синтаксис типа

identifier {
   type identifier ;
}

тьма.

VNN>Хотел бы посоветововаться с коллегами — насколько эта задача сложна? Руководство крайне недовольно, что ковыряюсь VNN>уже 3-й месяц и по моим планам выходит еще 2 с половиной.

Их можно понять, хотя конечно надо видеть что у вас там за язык на самом деле. По приведенному описанию — ничего такого, что бы тянуло на 5 месяцев работы нет.


VNN>Это действительно такая тривиальная задача и выпускник ВУЗа по специальности "программирование" нынче пишет свой VNN>компилятор за 2 дня?!!!

компилятор — это компилятор, а вот парсер/анализатор пишется быстро с использованием средств. Примеры парсеров C/C++ есть по моему, в любом генераторе парсеров — что в SPIRIT, что в ANTLR. Что мешало их взять и допилить?

И кстати, язык-то сам для чего?

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

VNN>По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — фактически только одни определения типов. Хотел бы посоветововаться с коллегами — насколько эта задача сложна?
Зависит от того, что конкретно нужно. Написать лексер/парсер несложно.
Я в свое время лексический/синтаксический анализатор + транслятор в С++ вот с примерно такого языка:

VIDEO v:"f:\\goal.avi";
FRAME f:v[1];

for_each(fram in v)
{
  for_each(pixe in fram)
  {
    PrintInt(pixe);
    Print("\t");
  };
};

SaveBMP("f:\\imptest.bmp",f);

написал за день(не рабочий, поболее) где-то до уровня волне рабочей альфа-версии полностью на С++ без всяких генераторов. Очень хотелось курсовой сдать
Естественно, никакой оптимизации, стандартной библиотеки, интероперабельности с другими языками.

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

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

AVK>>Я бы все таки советовал начать с LL парсеров, т.е. c antlr или CoCo/R

С>Хм, мне было проще пользоваться bison, чем antlr.

Дело не в простоте самого бизона или antlr (в этом плане CoCo/R как минимум не хуже, если так критично), а в том, что получается на выходе. Понять что делает LL парсер несложно, а вот разобратся в LALR ...

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

__>если у него там язык "похож на Си" (хоть и "проще") ("пока"), то LL ему не поможет

Ну, в плане мощности вряд ли LALR(1) сильно лучше LL(1), а antlr позволяет LL(k), и, даже LL(*) в 3 версии. Последний покрывает большинство разумных потребностей.

__> да и вообще.. мало что поможет

Почему? Базовая грамматика С-подобных языков ЕМНИП укладывается в LL(1) без особых проблем.

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

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

__>>если у него там язык "похож на Си" (хоть и "проще") ("пока"), то LL ему не поможет

AVK>Ну, в плане мощности вряд ли LALR(1) сильно лучше LL(1), а antlr позволяет LL(k), и, даже LL(*) в 3 версии. Последний покрывает большинство разумных потребностей.

Ну вообще, LARL(1) (он же LR(1), LARL — это всего лишь оптимизация размеров таблиц bottom-up парсера) эквивалентен по мощности LR(*), т.е. покрывает все детерминированные КС-языки. Правда, насчет разумных потребностей, Вам видней.

AndrewVK wrote:
>
> Здравствуйте, Сергей, Вы писали:
>
> AVK>>Я бы все таки советовал начать с LL парсеров, т.е. c antlr или CoCo/R
>
> С>Хм, мне было проще пользоваться bison, чем antlr.
>
> Дело не в простоте самого бизона или antlr (в этом плане CoCo/R как
> минимум не хуже, если так критично), а в том, что получается на выходе.
> Понять что делает LL парсер несложно, а вот разобратся в LALR ...

А что в LALR сложного? С LR же понятно, а LALR — это расширение класса
LR(0) грамматик, нечто среднее между SLR и LR(1).
Кстати, непонятно, зачем нужно разбираться с тем, что делает LALR парсер?

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

dmz>И кстати, язык-то сам для чего?
В одном из своих предыдущих постов я уже приводил ссылку на описание языка.

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

F>Не "красный дракон", а "книга дракона":
Пардон :-) Уже качаю, спасибо. :beer:

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

AVK>>Ну, в плане мощности вряд ли LALR(1) сильно лучше LL(1), а antlr позволяет LL(k), и, даже LL(*) в 3 версии. Последний покрывает большинство разумных потребностей.

kl>Ну вообще, LARL(1) (он же LR(1), LARL — это всего лишь оптимизация размеров таблиц bottom-up парсера)...

Пардон, засомневался, проверил и это действительно оказалось не совсем верно. Оптимизация таблиц в редких случаях может вносить reduce-reduce конфликты (т.е. есть грамматики ктр LR(1) но не LARL(1)).
здесь.

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

H>Тут нужно определиться с тем, какое представление вам хочется получить.
H>Наиболее естественное для yacc — это трансформация в связанный набор
H>классов, который затем можно преобразовать в что угодно.

H>Выглядит примерно так:
H>Берем исходную грамматику в BNF:

А вот уже что-то реальное — респект! Когда в самом начале работы сунулся читать некую доку по Яку стало грустно — время на освоение материала показалось чрезмерным.
Может посоветуете, как бы и не маразматично это звучало, какой-нибудь букварь типа "Yacc для чайников"?

kl wrote:
>
> AVK>Здравствуйте, _pk_sly, Вы писали:
>
> __>>если у него там язык "похож на Си" (хоть и "проще") ("пока"), то LL
> ему не поможет
>
> AVK>Ну, в плане мощности вряд ли LALR(1) сильно лучше LL(1), а antlr
> позволяет LL(k), и, даже LL(*) в 3 версии. Последний покрывает
> большинство разумных потребностей.
>
> Ну вообще, LARL(1) (он же LR(1), LARL — это всего лишь оптимизация
> размеров таблиц bottom-up парсера) эквивалентен по мощности LR(*), т.е.

По поводу LR(1) vs LALR(1) еще можно почитать описание bison, раздел
"Mysterious Reduce/Reduce Conflicts". Другое дело, что придумать
грамматику являющуюся LR(1), но не являющуюся LALR(1) достаточно сложно,
а то, что придумывается не выглядит практичным.
Вообще, и в самом деле, LL грамматик, обычно вполне достаточно, но LALR
проще в использовании, так как позволяет выражать больше типичных
языковых конструкций без модификаций. А результат гораздо проще
поддерживать и сопровождать. С другой стороны LL облегчает задачу
наличием наследуемых атрибутов.
И, кстати, C — вообще-то контекстно-зависимый язык (конструкция
преобразование типов). Но эти зависимости относительно легко разрешаются.

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

H>А что в LALR сложного? С LR же понятно

С LR тоже непонятно. Собственно из-за этого и вытекают проблемы в LR с error reporting и error recovery.

H>Кстати, непонятно, зачем нужно разбираться с тем, что делает LALR парсер?

Отлаживать как?

VadNuNik wrote:
>
> Здравствуйте, hexis, Вы писали:
>
> H>Тут нужно определиться с тем, какое представление вам хочется получить.
> H>Наиболее естественное для yacc — это трансформация в связанный набор
> H>классов, который затем можно преобразовать в что угодно.
>
> H>Выглядит примерно так:
> H>Берем исходную грамматику в BNF:
>
> А вот уже что-то реальное — респект! Когда в самом начале работы сунулся
> читать некую доку по Яку стало грустно — время на освоение материала
> показалось чрезмерным.
> Может посоветуете, как бы и не маразматично это звучало, какой-нибудь
> букварь типа "Yacc для чайников"?

Описание bison на русском подойдет?
http://www.linux.org.ru/books/GNU/bison/bison_toc.html

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

H>И, кстати, C — вообще-то контекстно-зависимый язык (конструкция
H>преобразование типов). Но эти зависимости относительно легко разрешаются.

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

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

H>Описание bison на русском подойдет?
H>http://www.linux.org.ru/books/GNU/bison/bison_toc.html

Эх ма... знать бы что за зверь этот бизон :-) Судя по обсуждению клон/вариант Яка?
Скачал "книгу дракона", кой-каких исходников, пойду покурю.
Самая моя большая ошибка (ну кроме той, что нужно было как-то отмазаться от этой работы сразу), что данную тему я не завел СРАЗУ как получил задание.
Если после провала проекта не уволят, учту на будущее :-)

AndrewVK wrote:
>
> Здравствуйте, hexis, Вы писали:
>
> H>И, кстати, C — вообще-то контекстно-зависимый язык (конструкция
> H>преобразование типов). Но эти зависимости относительно легко разрешаются.
>
> Тут в свое время по поводу этого был большой флейм. Контекстно свободной
> или контекстно зависимой может быть конкретная грамматика, а контекстная
> зависимость языка — вопрос разделения набора ограничивающих правил на
> лексические, синтаксические и семантические.

Согласен в той степени, что речь идет о разных вещах. В классической
теория синтаксического анализа, перевода и компиляции под языком
понимается нечто отличное от того, что под этим понимают программисты, а
именно (цитирую), язык — это множество всех цепочек конечной длины в
заданном алфавите. И говорят, что язык порождается (или определяется)
грамматикой. С этой точки зрения, язык и грамматика — практически
синонимы, в том плане, что определение контекстно-свободной или
контекстно-зависимой грамматики порождает соответствующий
контекстно-свободный или контекстно-зависимый язык.

VadNuNik wrote:
>
> Здравствуйте, hexis, Вы писали:
>
> H>Описание bison на русском подойдет?
> H>http://www.linux.org.ru/books/GNU/bison/bison_toc.html
>
> Эх ма... знать бы что за зверь этот бизон Судя по обсуждению
> клон/вариант Яка?

Да, это клон yacc от GNU. Практически полная совместимость по исходным
текстам. Есть, конечно, и отличия, в основном в деталях реализации, но
вряд ли это существенно. Кроме того, bison так-же можно найти (или легко
спортировать) под любую платформу.

> Скачал "книгу дракона", кой-каких исходников, пойду покурю.
> Самая моя большая ошибка (ну кроме той, что нужно было как-то отмазаться
> от этой работы сразу), что данную тему я не завел *СРАЗУ* как получил
> задание.
> Если после провала проекта не уволят, учту на будущее
Ну так хоть сейчас пишите. Может все еще и не так плохо.

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

VNN>Эх ма... знать бы что за зверь этот бизон Судя по обсуждению клон/вариант Яка?

Да, они очень похожи. Есть еще Jay — порт на C# и Java. Но я, учитывая твой опыт, по прежнему советую тебе поглядеть в сторону CoCo/R или antlr.

AndrewVK wrote:
>
> Здравствуйте, hexis, Вы писали:
>
> H>А что в LALR сложного? С LR же понятно
>
> С LR тоже непонятно. Собственно из-за этого и вытекают проблемы в LR с
> error reporting и error recovery.

Ну, тема ошибок — больная тема в LR вообще. Конечно в LL это гораздо
проще. Но, тем не менее, особых проблем вроде не возникает. Например,
можно использовать действия (actions) для определения контекста. Правда,
существует доказанная теорема о том, что если в LALR(1) анализаторе,
расширенном символами действия, каждое правило начинается с такого
действия, то язык, распознаваемый таким анализатором — LL(1). Но можно
ведь и не доводить до этого.

> H>Кстати, непонятно, зачем нужно разбираться с тем, что делает LALR парсер?
>
> Отлаживать как?

Все равно не понимаю. Отлаживать что? Если грамматику — для этого не
надо знать, как работает парсер. Или вы говорите о ручном написании
анализатора? Но причем тут выход того или иного генератора анализаторов?

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

H>Ну, тема ошибок — больная тема в LR вообще.

Это следствие сложной и неочевидной структуктуры получаемого парсера. Поэтому, если уж опыт в создании парсеров на 0, лучше (по крайней мере в коммерческом проекте) все таки попытаться уложится в LL(k).

H>Все равно не понимаю. Отлаживать что?

Парсер.

H> Если грамматику — для этого не надо знать, как работает парсер.

Я имею ввиду отладку всего комплекса — грамматики, рукописных разруливаний, которые в штатную грамматику не влезли и построителя ATS.

AndrewVK wrote:
>
> Здравствуйте, hexis, Вы писали:
>
> H>Ну, тема ошибок — больная тема в LR вообще.
>
> Это следствие сложной и неочевидной структуктуры получаемого парсера.
> Поэтому, если уж опыт в создании парсеров на 0, лучше (по крайней мере в
> коммерческом проекте) все таки попытаться уложится в LL(k).

Да нет. Это следствие самого принципа работы LR — его сила в анализе
оборачивается слабостью в определении текущего состояния по отношению ко
входному потоку. Для LL, соответственно, наоборот.

А вот про то, куда лучше уложиться — не знаю. Единственная проблема с
LALR — понимание как разрешать конфликты. Мне, конечно, хорошо помогло
знание алгоритмов LALR (точнее, тут нужно понимание механизма
LR(0)-ситуаций). С другой стороны, все те-же самые конфликты (и еще
дополнительные — грамматика-то уже) приходится решать в LL анализаторе —
фактически, можно сказать, что отладка большой грамматики сложна и там и
там. Но вот при использовании того-же CoCo/R, исходную грамматику точно
придется переписывать — он не делает никаких преобразований грамматики,
даже тех, что мог бы, ни устранения левой рекурсии, ни факторизации,
ничего. А значит, точно приходится переписывать грамматику, и иногда
нехило, и результат факторизации не очень то красив получается. ANTLR не
пользовался, а в PCCTS, насколько я помню, преобразований тоже не было.

В общем, я считаю, что это — дело личного вкуса и предпочтений. А для
новичка... ну, возможно ANTLR и лучше, но я ведь ничего про него не знаю
— как я могу сравнивать?

>
> H>Все равно не понимаю. Отлаживать что?
>
> Парсер.
>
> H> Если грамматику — для этого не надо знать, как работает парсер.
>
> Я имею ввиду отладку всего комплекса — грамматики, рукописных
> разруливаний, которые в штатную грамматику не влезли и построителя ATS.

Все, полазил по инету и понял, что под этим имеется в виду — возможность
трассировать исходный тексту в RDP. Не уверен, что это сильно актуально
— никогда не испытывал проблемы с этим в yacc.

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

H>>Кстати, непонятно, зачем нужно разбираться с тем, что делает LALR парсер?

AVK>Отлаживать как?

Не знаю как в самом yacc, но в ocamlyacc есть опция, при которой сгенерённый парсер в stdout пишет номера правил, по которым происходит сдвиг/свёртка. Этого + минимального представления того, как работает bottom-up парсер, вполне хватает. Что ещё отлаживать? То, как полученный AST обрабатывается? Это уже за пределами парсера. Построение самого AST? А что там отлаживать?

Лично я юзаю ocamlyacc и не жалуюсь. Проблем с отладкой нету. Хотя, и отладчика адекватного нету

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

H>Да нет. Это следствие самого принципа работы LR — его сила в анализе
H>оборачивается слабостью в определении текущего состояния по отношению ко
H>входному потоку.

Состояние то как раз определить несложно. Проблема его потом интерпретировать.

H>Мне, конечно, хорошо помогло знание алгоритмов LALR

Вот. Об этом и речь.

H>там. Но вот при использовании того-же CoCo/R, исходную грамматику точно
H>придется переписывать

Ее наверняка в любом случае придется переписывать, если не пользоваться чем то вроде Эрли или GLR.

H>ANTLR не пользовался

В 2 версии он тоже ничего такого не делал.

H>В общем, я считаю, что это — дело личного вкуса и предпочтений. А для
H>новичка... ну, возможно ANTLR и лучше, но я ведь ничего про него не знаю
H>- как я могу сравнивать?

Речь не об antlr, а о том, что новичку лучше начинать с LL парсеров, как с наиболее простых.

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

K>Не знаю как в самом yacc, но в ocamlyacc есть опция, при которой сгенерённый парсер в stdout пишет номера правил, по которым происходит сдвиг/свёртка. Этого + минимального представления того, как работает bottom-up парсер, вполне хватает. Что ещё отлаживать? То, как полученный AST обрабатывается? Это уже за пределами парсера. Построение самого AST? А что там отлаживать?

Вот смотри. Пишешь ты парсер. В какой то момент на одном из примеров результат работы неверный. Твои действия?

AndrewVK wrote:
>
> Здравствуйте, hexis, Вы писали:
>
> H>Да нет. Это следствие самого принципа работы LR — его сила в анализе
> H>оборачивается слабостью в определении текущего состояния по отношению ко
> H>входному потоку.
>
> Состояние то как раз определить несложно. Проблема его потом
> интерпретировать.

Я не об этом. А о том, что LL анализатор всегда отслеживает свое
состояние в грамматике — вы всегда знаем анализируемое правило (одно! —
эт оважно) и положение в нем. А в LR этого не происходит — максимум, что
мы может узнать — это то, что данный префикс соответствует такому-то
набору LR ситуаций, или, соответственно мы можем узнать множество правил
грамматики, который могли бы свернуться с использованием этого префикса.
Это и будет интерпретацией (ее можно посмотреть в отладочном файле,
выдаваемом yacc) — несколько, совершенно разрозненных, на первый взгляд,
правил. То есть это состояние анализатора будет помогать диагностировать
ошибку примерно так-же, как оно помогает разработчику диагностировать
причину конфликта.

>
> H>Мне, конечно, хорошо помогло знание алгоритмов LALR
>
> Вот. Об этом и речь.

Так я и LL неплохо знаю. Собственно с него и начинал — с RDP, затем
доморощенный компилятора анализаторов LL(1), а уж потом yacc/lex.

>
> H>там. Но вот при использовании того-же CoCo/R, исходную грамматику точно
> H>придется переписывать
>
> Ее наверняка в любом случае придется переписывать, если не пользоваться
> чем то вроде Эрли или GLR.

Не факт. Скорее всего для LALR изменений или не будет вообще, или их
будет мало (в основном правка глюков в исходной грамматике). А вот для
CoCo/R переписывать придется однозначно — грамматика содержит левую
рекурсию.

>
> H>ANTLR не пользовался
>
> В 2 версии он тоже ничего такого не делал.

А в 3-ей?

>
> H>В общем, я считаю, что это — дело личного вкуса и предпочтений. А для
> H>новичка... ну, возможно ANTLR и лучше, но я ведь ничего про него не знаю
> H>- как я могу сравнивать?
>
> Речь не об antlr, а о том, что новичку лучше начинать с LL парсеров, как
> с наиболее простых.

Если руками писать — то однозначно: да.

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

AVK>Но я, учитывая твой опыт, по прежнему советую тебе поглядеть в сторону CoCo/R или antlr.
Ща гуглану. Еще чайниковый вопрос если можно, все эти замечательные вещи как, собственно, использовать? Меня устроит только вариант библиотек в исходных кодах для включения в проект (что-то а-ля Boost), весьма жесткие требования на этот счет.

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

VNN>Меня устроит только вариант библиотек в исходных кодах для включения в проект (что-то а-ля Boost), весьма жесткие требования на этот счет.

Генерируемый CoCo/R парсер библиотек вообще никаких не использует, исходники для рантайма antlr наличествуют.

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

VNN>Ща гуглану. Еще чайниковый вопрос если можно, все эти замечательные вещи как, собственно, использовать? Меня устроит только вариант библиотек в исходных кодах для включения в проект (что-то а-ля Boost), весьма жесткие требования на этот счет.

boost::spirit ?
Очень доходчивий и грамотно постренный туториал.

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

K>>Не знаю как в самом yacc, но в ocamlyacc есть опция, при которой сгенерённый парсер в stdout пишет номера правил, по которым происходит сдвиг/свёртка. Этого + минимального представления того, как работает bottom-up парсер, вполне хватает. Что ещё отлаживать? То, как полученный AST обрабатывается? Это уже за пределами парсера. Построение самого AST? А что там отлаживать?

AVK>Вот смотри. Пишешь ты парсер. В какой то момент на одном из примеров результат работы неверный. Твои действия?

Результат неверный где? В парсере? Т.е. имеется средство визуализации AST, и оно показывает, что по такому-то тексту AST построился неправильно? Тогда ошибка в грамматике, и трассировки указанным способом должно хватить. Например, можно составить спец. пример и посмотреть, везде ли правильно производится сдвиг/свёртка. Может, там, где ожидался сдвиг, происходит свёртка? Или наоборот?

Хотя обычно хватает посмотреть предупреждения которые вылазят в .output-файле.

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

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

K>Результат неверный где? В парсере? Т.е. имеется средство визуализации AST, и оно показывает, что по такому-то тексту AST построился неправильно?

Да. Либо выдается ошибка, там где она не должна выдаваться, или наоборот, там где должна — не выдается.

K> Тогда ошибка в грамматике

Или в построителе AST. Или в логике кастомного анализатора ошибочных ситуаций. Или в логике кастомно дописанного парсера для конфликтов, парсером не разрешаемых.

K>, и трассировки указанным способом должно хватить.

Т.е. тупо глазами анализировать грамматику? А в LL парсере я просто поставлю точку останова и в отладчике досконально изучу, что и как работает. Причем одновременно буду смотреть и собственно парсер грамматики, который генератор сделал, и построитель AST, который я руками написал, и все остальное.

K>Хотя, надо сказать, не заметил особых средств автоматизации этого дела в LL-парсерах.

Ну кое что в antlr есть, но дело не в средствах автоматизации, а в сложности этого рукописного кода.

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

АК>boost::spirit ?
АК>Очень доходчивий и грамотно постренный туториал.

Оч интересно. Спасибо. Материала набрал море, успеть бы "зисть" :-)

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

K>> Тогда ошибка в грамматике

AVK>Или в построителе AST.

Где в нём может быть ошибка?

AVK> Или в логике кастомно дописанного парсера для конфликтов, парсером не разрешаемых.

Не помню, чтобы когда-либо встречался с оными в случае с LALR.

K>>, и трассировки указанным способом должно хватить.

AVK>Т.е. тупо глазами анализировать грамматику?

Т.е. тупо анализировать последовательность сдвигов/свёрток. А что, отладка _программ_ — это уже не отладка последовательности действий?

AVK> А в LL парсере я просто поставлю точку останова и в отладчике досконально изучу, что и как работает.

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

K>>Хотя, надо сказать, не заметил особых средств автоматизации этого дела в LL-парсерах.

AVK>Ну кое что в antlr есть, но дело не в средствах автоматизации, а в сложности этого рукописного кода.

Кое-что и в YACC есть.

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

AVK>>Или в построителе AST.

K>Где в нём может быть ошибка?

Где угодно, как и в любом другом коде.

AVK>> Или в логике кастомно дописанного парсера для конфликтов, парсером не разрешаемых.

K>Не помню, чтобы когда-либо встречался с оными в случае с LALR.

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

AVK>> А в LL парсере я просто поставлю точку останова и в отладчике досконально изучу, что и как работает.

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

Есть только небольшая разница между LL, который практически идентичен грамматике, и LR, который просто автомат, на каждом щшаге которого надо сверять его состояние с таблицами и разбираться, что в данный момент происходит. Это примерно то же самое, что и отладка шарповских yield по сравнению с отладкой того, что в итоге из этих yield компилятор нагенерирует.

AndrewVK wrote:
>
> AVK>> А в LL парсере я просто поставлю точку останова и в отладчике
> досконально изучу, что и как работает.
>
> K>Если есть проблемы с кодом, который выполняется при свёртке, я тоже на
> нём пославлю брейкпоинт в отладчике и досконально изучу, что и как работает.
>
> Есть только небольшая разница между LL, который практически идентичен
> грамматике, и LR, который просто автомат, на каждом щшаге которого надо
> сверять его состояние с таблицами и разбираться, что в данный момент
> происходит. Это примерно то же самое, что и отладка шарповских yield по
> сравнению с отладкой того, что в итоге из этих yield компилятор
> нагенерирует.

Думаю, что проблема не в алгоритме разбора, а в недостаточном понимании
основ LALR, в привычке к LL и в привычной технологии отладки. Я вообще
при поиске ошибок редко начинаю с *трассирования* кода или грамматики.
Обычно достаточно понять в каком состоянии находится парсер, иногда
выяснить предисторию, а потом продумать это место. Обычно это помогает
устранить проблему на более высоком уровне — например, так, чтобы не
поломать чего-то другого, или найти другие, связанные проблемы.

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

VNN>По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — фактически только одни определения типов. Хотел бы посоветововаться с коллегами — насколько эта задача сложна? Руководство крайне недовольно, что ковыряюсь уже 3-й месяц и по моим планам выходит еще 2 с половиной.

Зависит от опыта. Причем как от опыта программирования вообщем, так (и даже в первую очередь) от опыта разработки парсеров. Спец может и за пару дней накатать что-то рабочее. Особенно если он использует наработки или построители парсеров.

VNN>Пришлось самостоятельно описывать грамматику языка, пробовал воспрльзоватсья какимими то существующими наработками типа YACC и LEX, но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям.

Зря. Особенно если нет опыта написания рукописных парсеров.

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

Мой тебе совет. Выбери построитель парсеров наиболее подхдящий для языка реализации и используй его. Недели две на освоение, а грамматики для С на каждом углу валяются... Скажем для Явы это будет однозначно ANTLR, для дотнета ANTLR же или CocaR. Яки не советую, так как они только для С и пригодны. А на более сложных грамматиках начинаются проблему связанные с LALR(1)-алгоритмом. Если пишеш на С/С++, то можно выбрать Бизон. Это улучшенный Як.

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

VD>Зря. Особенно если нет опыта написания рукописных парсеров.
К сожалению, у меня не только небыло опыта написания подобных вещей, но и даже про теорию я не особо знал. Сейчас что-то поверхам похватал. Я до сих пор внятно не представляю КАК собствено использовать всевозможные Яки, Бизоны и прочих "копытных" в моем проекте. Как мне тут уже подсказали, нужно описать все BNF-выражения языка (они уже есть) сначала в виде своих классов, потом в виде некого кода Яка и прочих, а вот последующие шаги в тумане.

VD>Твои разсуждения о иерархиях классов и затраченом времени для стольк простого языка наводят на мысль, что ты в этом далеко не спец.
Пишу на С++ за еду :) Парсеры и компиляторы никогда не писал, даже во время учебы — не входило в скудный курс программирования (АСУ).

VD>Мой тебе совет. Выбери построитель парсеров наиболее подхдящий для языка реализации и используй его.
Вот, опять. КАК "использовать"-то? :-) Можно в 3-4-х пунктах описать как оно ваще работает? Вопчем, в итоге, я уже смастерил собственный алгоритм синтаксического разбора, не знаю насколько он оптимален — еще не кодил. Из препроцессинга пока реализовал только удаление каментов всех типов, пустот, непечатываемых символов. Подлючаемые файлы на первый взгляд сложности не представляют, но на первом этапе они особо то и не нужны. Во всяком случае я представляю как я прверащу файл с кодом в собственную модель данных, а вот как то же самое сделать при помощи стороннего парсера не знаю. Все же склоняюсь к тому, что на переправе коней не меняют и буду додавливать то как начал, если получится то потом, когда будет время прочту пару книжек по компиляторами вероятно переделю.

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

K>Ну ты бы почитал документацию что ли. Туториалы какие-нибудь, и всё стало бы ясно.
Да нужно. Есть уже и книжки и доки... но время :-(((

K>Во-первых, как правило в компиляторах парсер работает в два этапа. Первый этап — лексический разбор. На этом этапе текст разбивается не лексемы — идентификаторы, числа, строки,
Принцип разбора — грубо я уже понял. Я не врублюсь как это все выглядит в "мясе". Ну в реальной программе. Если бы речь шла про консоль и на выходе мне нужно было бы получить некий код для последующей компиляции это одно, тут ясно. У меня программа представляет из себя грубо говоря IDE, т.е. мне нужно загрузить в нее файл на OIL, если в нем есть ошибки — показать их, если нет — отобразить описанную кодом систему визуально. В какое место тут пихать "генератор компилятора" мне не совсем ясно.

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

K>>Во-первых, как правило в компиляторах парсер работает в два этапа. Первый этап — лексический разбор. На этом этапе текст разбивается не лексемы — идентификаторы, числа, строки,
VNN>Принцип разбора — грубо я уже понял. Я не врублюсь как это все выглядит в "мясе". Ну в реальной программе. Если бы речь шла про консоль и на выходе мне нужно было бы получить некий код для последующей компиляции это одно, тут ясно. У меня программа представляет из себя грубо говоря IDE, т.е. мне нужно загрузить в нее файл на OIL, если в нем есть ошибки — показать их, если нет — отобразить описанную кодом систему визуально. В какое место тут пихать "генератор компилятора" мне не совсем ясно.

Тогда не совсем понятно, что именно тебя интересует? Диагностика ошибок? На этапе синтаксического анализа можно выявить синтаксические ошибки. Семантические ошибки выявляются в процессе дальнейшей обработки. Или ты не можешь организовать GUI? Что не получается?

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

K>Это автоматизируется lex'ом. Каждый класс лексем можно описать регулярным выражением. При этом рядом с каждым регулярным выражением ставится семантическое правило

В большинстве случаев в лексере все таки обходятся без семантики или с минимумом ее.

K>Этот этап автоматизируется yacc.

Не весь этап, а анализ правил. Построение AST (за редкими исключениями вроде antlr) — это уже задача программиста.

K> Чтобы описать синтаксис языка, регулярных выражений не хватает. Тут уже нужны так называемые контекстно-зависимые грамматики

Это у тебя в LALR парсере контекстно зависимая грамматика???
Ты, видимо, перепутал контекстно-свободные и регулярные грамматики.

K>К сожалению, yacc не поддерживает BNF
http://en.wikipedia.org/wiki/Yacc

It generates a parser (the part of a compiler that tries to make syntactic sense of the source code) based on an analytic grammar written in a notation similar to BNF.

K>, и грамматику ему надо задавать практически в том же виде, как определено в математике.

В математике (если речь о теории формальных грамматик) как раз BNF чаще всего и используется.

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

VNN>По работе пишу парсер/синтаксический/семантический анализатор языка. Внешне похож на С, но сильно проще (пока) — фактически только одни определения типов. Хотел бы посоветововаться с коллегами — насколько эта задача сложна? Руководство крайне недовольно, что ковыряюсь уже 3-й месяц и по моим планам выходит еще 2 с половиной.
VNN>Пришлось самостоятельно описывать грамматику языка, пробовал воспрльзоватсья какимими то существующими наработками типа YACC и LEX, но разбиратся с ними показалось еще сложнее и явно из пушки по воробьям. Ща ковыряю синтаксический анализ, процесс идет тяжко. Это действительно такая тривиальная задача и выпускник ВУЗа по специальности "программирование" нынче пишет свой компилятор за 2 дня?!!!

Я уже что-то подобное делал, на perl, используя yapp (yet another parser parser).
Ушло — не помню уже сколько. наверное порядка 1-3 месяцев по 1-2 часа в день.
Свяжишь со мной по майлу, попробую помочь.
Интересует что конкретно что ты пишешь и синтакс твоего языка.
Предпочтительно не хотелось бы ничего отдавать бесплатно — если вы будете дальше дорабатывать
то хотелось бы получить доработки обратно.

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

T>Интересует что конкретно что ты пишешь и синтакс твоего языка.
Уфф... тут выше по треду я уже раза 3 ссылку на описание языка давал — это OIL.

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

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

АК>>boost::spirit ?
АК>>Очень доходчивий и грамотно постренный туториал.

VNN>Оч интересно. Спасибо. Материала набрал море, успеть бы "зисть"

Совет от того кто пробовал это все — не трать времени на yacc, lex,
boost примочки. первые 2-е слишком плохо продуманы, и делание языка на них напоминает
создание ракеты, где ты сам закручиваешь каждый болтик.

boost — будешь копаться в темплайтах ошибках до опупения.
боост темплайты — это убийцы скорости компиляции.
wave c++ parser (основан на boost spirit) 1 рекомпиляция занимала у меня
2-5 минут без какий либо изменений в коде.
Ошибки boost темплайты выдают такие что хоть стой хоть падай.

perl / yapp самые простые в использовании.

wine (windows emulation) содержит какой то idl compiler,
и samba v4 (file sharing server) тоже содержит компилер.
(Оба основаны на yapp)

Внимательно смотри на лицензии которые там применяются,
очень часто если оттуда что то возмешь — потом надо будет весь
свой проэкт публиковать в инете (GPL лицензии).

Советую копировать идеи, но не их имплементации.

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

K>Тогда не совсем понятно, что именно тебя интересует? Диагностика ошибок? На этапе синтаксического анализа можно выявить синтаксические ошибки. Семантические ошибки выявляются в процессе дальнейшей обработки. Или ты не можешь организовать GUI? Что не получается?

Погодь. Опишу по пунктам что мне нужно:
1. Читать программу на OIL
1.1 Выявлять синтаксически ошибки
1.2 Выявлять семантические ошибки
2. Отображать визуальное представление программы (ну грубо говоря как форма представляется на C# или Builder/Delphi)
2.1 Визуальными средствами призводить редактирование.

В данный момент меня интересует не ГУЙ, тут как раз проблем мне видется меньше всего, а пункты 1.1 и 1.2. Я разработал свои собственные алгоритмы, чую сделал кривоватый велосипед, но вот куда в моей системе запихнуть Яка, Бизона или еще какого зверя я не пойму. Везде пишут про "генерацию компилятора" и как я понимаю результатом работы является исходный код, который нужно компилить уже обычным (ну С++ например) компилятором для получения чего-то... чего? Прошу прощения, что буквари так и не почитал, уже писал, что бросать наработки не хочется. Но вероятно, если нормально сдам первый этап программы, уже в более спокойной обстановке хочу передалать все по правильному, потому и тему активно развиваю.

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

> Везде пишут про "генерацию компилятора" и как я понимаю результатом работы является исходный код, который нужно компилить уже обычным (ну С++ например) компилятором для получения чего-то... чего?

Получишь код, который будет получать поток исходного кода, а на выходе будет выдавать статически типизованное AST. Ещё неплохо если будет подготовлена инфраструктура для обхода Посетителем. А там до интерпретатора уже рукой подать.

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

AVK>Это у тебя в LALR парсере контекстно зависимая грамматика???
AVK>Ты, видимо, перепутал контекстно-свободные и регулярные грамматики.

Очепятался. Должно было быть "контекстно-свободная грамматика"

K>>К сожалению, yacc не поддерживает BNF
AVK>http://en.wikipedia.org/wiki/Yacc
AVK>

It generates a parser (the part of a compiler that tries to make syntactic sense of the source code) based on an analytic grammar written in a notation similar to BNF.

Не на столько и similar. Многие фишки из EBNF яки не поддерживают.

K>>, и грамматику ему надо задавать практически в том же виде, как определено в математике.

AVK>В математике (если речь о теории формальных грамматик) как раз BNF чаще всего и используется.

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

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

D>Получишь код, который будет получать поток исходного кода
Не совсем себе представляю, как его потом обрабатывать в run-time?

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

VNN>Не совсем себе представляю, как его потом обрабатывать в run-time?

Написал грамматику, сгенерил парсер, скомпилял его и добавил в основной проект. Самое примитивное — обход AST посетителем и вычисление результатов. Например имеешь код:

a = b + 1

Допустим раскладывается (упрощённо) на:
Statement
Assignment
LValue
Var // a
RValue
AddOp
Operands
Var //b
IntegerLiteral

Обходишь это дерево. Каждая нода вызывает посетителя для дочерних нод, а потом обрабатывает результат. Например обработчик Var(a) вернёт (type:double, value:2.0), a обработчик IntegerLiteral вернёт (type:integer, value:1). Обработчик AddOp берёт типы и значения операндов, обрабатывает их и возвращает результат.

Правильные генераторы добавляют вспомогательный код для обхода и можно сделать так (крайне упрощённо):
class MyAstVisitor {
public VisitorResult visitAddOp(AddOpNode node) {
VisitorResult result = new VisitorResult(double, 0.0);
for (Node childNode : node.getOperands()) {
VisitorResult childResult = childNode.visit(this);
// Тут разруливание типов с проверкой, приведением и т.п.
result.setValue(result.getValue() + childResult.getValue())
}
}

public VisitorResult visitIntegerLiteral(IntegerLiteralNode node) {
return new VisitorResult(integer, Integer.parse(node.text));
}
}

Ещё раз подчеркну, что это примитивное изложение, но очень быстро имплементируемое. Мне довелось сделать простой expression-evaluation-engine на Java с поддержкой массивов, функций, основных математических операций и типов данных за день.

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

VNN>Не совсем себе представляю, как его потом обрабатывать в run-time?

Всё зависит от того, какую именно часть семантики нужно проверить. Даже не знаю, что посоветовать. Лично у меня сложности с такими задачами закончились с изучениям ФЯ. Что тебе посоветовать, даже не знаю.

Ну, например, в том же околопаскале можно такми образом проверить наличие return'ов во всех ветвях:

type operator =
    Return_op   of expr
  | If_of       of expr * operator * operator option
  | While_op    of expr * operator
  | Multiple_op of operator list
  | и т.д

let check_returns node = match node with 
    Return_op _                     -> true
  | If_op(_, first, Some second)    -> check_returns first && check_returns second
  | If_op(_, first, None)           -> check_returns first
  | While_op(_, op)                 -> check_returns op
  | Multiple_op lst                 -> List.fold_left (fun (acc, e) -> acc || check_returns e) false lst
  | _                               -> false

В терминах C превращается во что-то вроде:

#define TRUE          1
#define FALSE         0

#define NODE_IF       0
#define NODE_WHILE    1
#define NODE_RETURN   2
#define NODE_MULTIPLE 3
// и т.д

typedef union tag_OperatorData
{
    struct
    {
        struct tag_Expr *cond;
        struct tag_Operator *first;
        struct tag_Operator *second;
    } if_op;
    struct
    {
        struct tag_Expr *predicate;
        struct tag_Operator *op;
    } while_op;
    struct
    {
        struct tag_Expr *expr;
    } return_op;
    struct
    {
        struct tag_Operator **operators;
        int count;
    } multiple_op
} OperatorData;

typedef struct tag_Operator
{
    int type;
    OperatorData data;
} Operator;


int check_returns(Operator *op)
{
    switch (op->type)
    {
        case NODE_RETURN:
            return TRUE;
        case NODE_IF:
            if (op->data.if_op.second != NULL)
                return check_returns(op->data.if_op.first) && check_returns(op->data.if_op.second);
            else
                return check_returns(op->data.if_op.first);
        case NODE_WHILE:
            return check_returns(op->data.while_op.op);
        case NODE_MULTIPLE:
            for (int i = 0; i < op->data.multiple_op.count; ++i)
                if (check_returns(op->data.multiple_op.operators[i]))
                    return TRUE;
            return FALSE;
        default:
            return FALSE;
    }
}

Где-то так. Можно усложнить пример. Например, можно возвращать не bool, а список тех строк, в которых найдена ошибка. Или, что лучше в случае с C — завести императивную процедуру, которая просто добавляет сообщения об ошибке в лог. Сразу скажу: для этого нужно модифицировать структуру Operator, добавив туда информацию о координатах узла в тексте (начало, конец, имя файла), или в ML к каждому конструктору алгебраического типа добавить location в качестве параметра. Разумеется, надо будет соотв. образом модифицировать парсер.

VadNuNik wrote:
>
> K>Тогда не совсем понятно, что именно тебя интересует? Диагностика
> ошибок? На этапе синтаксического анализа можно выявить синтаксические
> ошибки. Семантические ошибки выявляются в процессе дальнейшей обработки.
> Или ты не можешь организовать GUI? Что не получается?
>
> Погодь. Опишу по пунктам что мне нужно:
> 1. Читать программу на OIL
> 1.1 Выявлять синтаксически ошибки
> 1.2 Выявлять семантические ошибки
> 2. Отображать визуальное представление программы (ну грубо говоря как
> форма представляется на C# или Builder/Delphi)
> 2.1 Визуальными средствами призводить редактирование.
>
> В данный момент меня интересует не ГУЙ, тут как раз проблем мне видется
> меньше всего, а пункты 1.1 и 1.2. Я разработал свои собственные
> алгоритмы, чую сделал кривоватый велосипед, но вот куда в моей системе
> запихнуть Яка, Бизона или еще какого зверя я не пойму. Везде пишут про

Весь вопрос заключается в том, как представлена (или предполагается быть
представленной) информация для пунктов 1.2 или 2.*. Что это — набор
связанных структур в памяти, внешнее структурированное хранилище? Но
что-то должно быть. А компилятор, на чем бы он не был написан, нужен,
чтобы транслировать внешнее (текстовое) представление во внутреннее — в
то, что используется для пунктов 1.2 и 2.*

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

D>Написал грамматику, сгенерил парсер, скомпилял его и добавил в основной проект. Самое примитивное — обход AST посетителем и вычисление результатов. Например имеешь код:
Да как писать все самостоятельно ясно :-) Тут же 4/5 треда о том, что самому давить клаву в этом деле следует только в учебных целях, а реальные пацаны используют уже готовые механизмы только обучая их своему языку. Вот я о том и спрашивал — как использовать yacc-образные механизмы в проекте, представляющем исходный код в некой промежуточной структуре данных, которую нужно редактировать в run-time. То, что посититель для анализа кода удобен я знаю, собственно, в "букваре" это даже в качестве примера рассмотрено :-)

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

AVK>Дракона уже начал читать?
Ага :-)

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

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

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

K>Ну, например, в том же околопаскале можно такми образом проверить наличие return'ов во всех ветвях:
Это что-то типа yacc-а?

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

K>>Всё зависит от того, какую именно часть семантики нужно проверить.
VNN>Проверять надо бы все и синтаксическую верность кода и потом уже семантику языка — правильное использование типов данных, правильность их определения и пр.

Синтаксическая корректность кода проверяется парсером, сгенерённым yacc'ом. Правда, для этого в самом y-файле, скармливаемому yacc'у надо сделать некоторые спец. указания с символом error. Как это делается — см. в документации по yacc'у (а лучше, по bison'у).

K>>Ну, например, в том же околопаскале можно такми образом проверить наличие return'ов во всех ветвях:
VNN>Это что-то типа yacc-а?

Околопаскаль — это выдуманный язык, предназначенный для иллюстрации того, как пишется парсер. Код приведён на ML — таком же ЯП, как C, Pascal и т.п. Ещё ниже приведён абсолютно аналогичный код на Pascal. Ты же спросил — что делать с результатом, выданным yacc'ом, я и показал пример. А так, зависит от задачи.

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

VNN>как использовать yacc-образные механизмы в проекте, представляющем исходный код в некой промежуточной структуре данных, которую нужно редактировать в run-time

yacc используется для генерации кода, который формирует этой промежуточную структуру. Кстати, она называется AST.

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

Ладно, спасибо большое за совет, чую без прочтения букваря более внятного вопроса я сформулировать не смогу :)

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

H>Весь вопрос заключается в том, как представлена (или предполагается быть
H>представленной) информация для пунктов 1.2 или 2.*. Что это — набор
H>связанных структур в памяти, внешнее структурированное хранилище?
Какая именно информация? У меня есть файлы на OIL (ну и моя программ должа уметь сама их конструировать), есть мной созданное описание языка в виде XML-документа, есть модель языка, которая читает этот XML. Есть код очищающий исходники от "мусора", долизываю алгоритмы (начал кодить потехоньку) разбора кода на лексемы и последующего семантического анализа выражений языка, ко всему этому приделана примитивная сигнализация об ошибках — на первой же синтаксической ошибке парсер остановится, семантические пойдут типа как предупреждения.

H>что-то должно быть. А компилятор, на чем бы он не был написан, нужен,
H>чтобы транслировать внешнее (текстовое) представление во внутреннее — в
H>то, что используется для пунктов 1.2 и 2.*
Для этого мне нужно его:
1. Обучить грамматике исходного языка
2. Обучить моим внутренним моделям данных
3. Каким-то образом все интегрировать в одну программу

Я правильно понял?

Видимо я неправильно понял вопрос. Или он был недостаточно конкретен.

Насчёт конкретно yacc — не подскажу. Он уже давно вымыт из мозга. Я предпочитаю LL-грамматики.