Парсер/лексический анализатор...

Ух, блин, америку открыл А-то я не знал. В драгон-буке это все и написано. Сегодня прочел Надо еще посылку нопа просмотреть и за недельку, не спеша, можно будет что-нибудь простенькое налабать. С таблицей символов и простеньким лексическим анализатором.

 

По-прежнему в голове слегка сумбурно... Значит так, лексический анализатор будет написан на основе JLex



взять тут:

http://www.cs.princeton.edu/~appel/modern/java/JLex/



Синтаксис у этой штуки примерно такой же как и у предлагаемых Sten'ом утилит.

Лексический анализатор используется только для парса хедера файла. Для парса собственно тела файла юзается стандартный

Код (Text):

1.  
2. while ((line = rdr.readLine()) != null)
3.  

Теперь то, что до сих пор не совсем понятно мне. Т.к. captain cobalt буквоедством занялся непоследовательно и не до конца



Вопрос:



Во входном файле есть три секции:

Код (Text):

1.  
2. %objects
3. %common
4. %keywords
5.  

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

 

Пытаюсь налабать файл спецификации... Голова пухнет

Проблемка тут с возможными конфликтами... Что возникнет при таком конфликте я даже и не знаю пока...

Вот попытка что-то налабать... Правда, пока не очень рабочее.

Код (Text):

1.  
2. /*** User code ***/
3.  
4.  
5. %%
6. /*** JLex directives ***/
7. DIGIT=          [0-9]
8. LETTER=         [a-zA-Z]
9. UNDERSCORE=     [_]
10. SPACE=          [\ \f\t\b\r\n]
11. OPEN_CURL_BRACKET=  [\{]
12. CLOSE_CURL_BRACKET= [\}]
13. HANDLER_NAME=       ({LETTER}|{UNDERSCORE})*
14. HANDLER_DATA=       \(({LETTER}|{DIGIT}|\||{UNDERSCORE})*\)
15. SECTION_HEADER=     %|({LETTER})*
16.  
17. %line
18.  
19. %%
20. /*** Regular expression rules ***/
21. {OPEN_CURL_BRACKETT}    {java.lang.System.out.println("Opening bracket: " + yytext()); }
22. {CLOSE_CURL_BRACKET}    {java.lang.System.out.println("Opening bracket: " + yytext()); }
23. {HANDLER_NAME}  {java.lang.System.out.println("Handler name: " + yytext()); }
24. {HANDLER_DATA}  {java.lang.System.out.println("Handler data: " + yytext()); }
25. {SECTION_HEADER}{java.lang.System.out.println("Section header: " + yytext()); }
26. {SPACE}*    { }
27. .       { java.lang.System.out.println("Don't know what to do with: " + yytext()); }
28.  

Вопросы:

1)HANDLER_NAME должно матчить имена типа BIND_loc_site_source, Author и т.п. Я пока не уверен, что регулярка правильная.

2)С HANDLER_DATA вообще мрак. Все дело в том, что регулярка может элементарно содержать и пробелы, например:



Author (me, me again, aaa|bbb|12354|hehe@he.com)

Тут, случаем, нет конфликта со SPACE?

 

Кстати, в случае HANDLER_DATA лексический анализатор должен выдать только данные, без скобок, т.е. дано на вход (me, me again, aaa|bbb|12354|hehe@he.com), а выдается только me, me again, aaa|bbb|12354|hehe@he.com.

 

Переделал маленько...

Код (Text):

1.  
2. /*** JLex directives ***/
3. DIGIT=          [0-9]
4. LETTER=         [a-zA-Z]
5. UNDERSCORE=     _
6. SPACE=          [\ \f\t\b\r\n]
7. OPEN_CURL_BRACKET=  \{
8. CLOSE_CURL_BRACKET= \}
9. HANDLER_NAME=       [{UNDERSCORE}{LETTER}]*
10. HANDLER_DATA=       [\(({DIGIT}{LETTER}{UNDERSCORE}\ \\|,@})\)]*
11. SECTION_HEADER=     [%{LETTER}]*
12.  

 

volodya> Хотелось бы, чтобы порядок следования мог быть любым...

volodya> Я правильно понимаю, что это работа драйвера лексического анализатора?



Нет, неправильно. Это пойдёт в синтаксис.

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



Поэтому - для каждой секции написать синтаксическое правило.



volodya> С HANDLER_DATA вообще мрак... может ... содержать и пробелы

volodya> лексический анализатор должен выдать только данные, без скобок...



Это более серьёзно.

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



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



Если так, то скобки, несомненно, пойдут на уровень синтаксиса.



Всё остальное можно реализовать разными способами.



Лексический анализатор, действительно, можно "научить" отличать "значащие" пробелы от "незначащих". Однако для этого ему необходима некоторая "зацепка". В качестве такой зацепки могут выступать запятые\скобки, ограничивающие каждый элемент данных. То есть, будет лексическое правило: нечто, ограниченное скобками\запятыми - это элемент данных, который необходимо обрабатывать как единое целое вместе со внутренними пробелами...



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

 

Мне кажется это довольнатаки интерестный вопрос ... может быть создать отдельную тему мол "Создания компилятора с 0" и объяснить и теорию и практику... как что куда и зачем... (в сети есть подобные темы но всё таки можно сделать всё очень конкретно и понятно) необязательно создовать компилятор и тди тп.. а просто научится парсить файл .. и тому подобное....



п.с: ну если затея не интерестно то удалите чтоль ответ мой....

 

Нет, неправильно. Это пойдёт в синтаксис.



По-моему, мы говорим об одинаковых вещах, но на разных языках...

Еще раз.

От лексического анализатора я ожидаю одно - набор токенов. Не более, не менее. Как поступать с этими токенами - лексический анализатор не знает. Для этого нужна логика более высокого уровня. Например, пусть псевдокод выглядит так:



String token lexan(void); - типа метод класса, который возвращает токен.



Вот я в цикле опрашиваю lexan(). Где-то так:

Код (Text):

1. if (lexan() == "SECTION_HEADER")

- мы встретили хедер секции, теперь ждем скобку (фигурная открывающая)

Код (Text):

1. do
2. {
3. ;
4. }while(lexan() != '{');

теперь ждем имена хендлеров + данные - опять lexan. И так до закрывающей фигурной скобки.



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



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

 

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





Так, о великий! Ты прав



Если так, то скобки, несомненно, пойдут на уровень синтаксиса.



А поподробнее? Как выглядит процесс?

 

> От лексического анализатора я ожидаю одно - набор токенов. Не более, не менее.



Абсолютно правильно.



> Вот я в цикле опрашиваю lexan(). Где-то так:

> if (lexan() == "SECTION_HEADER")



Тот, кто получает от lexan набор токенов, называется синтаксический анализатор.



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



> А поподробнее? Как выглядит процесс?



В языках программирования бывают строковые константы. Они ограничиваются кавычками. Эти константы опознаёт по кавычкам лексический анализатор. При этом кавычки он "съедает" и собственно константу отдаёт без них. Кроме лексического анализатора в таком компиляторе вообще "никто" "не знает", что строки ограничены кавычками. Синтаксический анализатор и вовсе получает только код "строковая константа".



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

 

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



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

 

Да?

А кто будет отделять друг от друга параметры?

Синтаксический анализатор?

А как он это будет делать?

Анализировать по одной букве?

Не кажется ли, что дважды анализировать один и тот же фрагмент по одной букве "неэкономично"?

 

А кто будет отделять друг от друга параметры?



Хендлер. Он знает, что куда пихать. Более того, для каждого хендлера могут быть свои правила. Так что, от лексера надо лишь подать то, что в скобках, без изменений. Вот и все.



Не кажется ли, что дважды анализировать один и тот же фрагмент по одной букве "неэкономично"?



Думаю, вопрос снят.

 

Токен - это синтаксически неделимая единица.



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

 

Хм... Ну тогда все значительно усложняется. Опять таки, строка для хендлера вполне может содержать пробелы. Как поступать в таком случае? И плевать мне, что подход будет неклассическим... Зачем самому себе устраивать головомороку?

 

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



А правила хендлера == синтаксические правила.

 

Пардон, не пойду по твоей дороге. Все, что в скобках - подается на вход хендлеру. Точка.



За дискуссию и прояснение некоторых моментов для меня - большое тебе спасибо.



В качестве генератора лексического анализатора буду юзать Jlex. Он похож на lex/flex. Роль синтаксического анализатора будет играть моя собственная логика + хендлеры. Такая архитектура вполне для меня удобна и логична. Хендлер "сам" решает в каком формате данные должны поступать на вход. Дело лексера - их ему предоставить.

 

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



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



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



> Пардон, не пойду по твоей дороге. Все, что в скобках - подается на вход хендлеру. Точка.



имхо, было бы проще

 

Может быть, я уже просто не могу понять, что ты хочешь до меня донести.



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





Да, это правда. Запятые используются для разделения параметров.

Как это дело происходит сейчас.



Вот, что я получаю из движка:

Код (Text):

1.  
2.     public static final int initCommonHandlers(String h_name, String h_data)
3.     {
4.         if(h_name.indexOf("Author") != -1)
5.             return processAuthor(h_data);
6.  
7.         if(h_name.indexOf("BIND_pub_object") != -1)
8.             return processPubObject(h_data);
9.  
10.         if(h_name.indexOf("BIND_Interaction_division") != -1)
11.             return processDivision(h_data);
12.  
13.         return -1;
14.     }
15.  

String h_name - название хендлера

String h_data - данные, передаваемые хендлеру.



Например, хендлер Author.

Код (Text):

1.  
2.     private static int processAuthor(String h_data)
3.     {
4.         String[] fields = h_data.split("[,]");
5.             //и так далее - работа с полями
6.         }
7.  

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

 

Ну дык, если лексический анализатор мне станет отдавать h_data, то ничего для меня не изменится. Не надо будет ничего переписывать, кроме собственно движка парсера. Вот и все. А то, что ты предлагаешь ведет к переписыванию очень многих вещей... И смысла я не вижу, что самое главное!