Как эффективно построить интерпретатор (лексер + парсер) в C? - PullRequest
Новая
       39

Как эффективно построить интерпретатор (лексер + парсер) в C?

8 голосов
/ 20 мая 2010

Я пытаюсь создать метаязык для написания кода разметки (например, xml и html), который может быть непосредственно встроен в код C / C ++. Вот простой пример, написанный на этом языке, я называю его WDI (интерфейс веб-разработки): 

 /*
  * Simple wdi/html sample source code
  */
 #include <mySite>

 string name = "myName";
 string toCapital(string str);

 html
 {
  head {
   title { mySiteTitle; }
   link(rel="stylesheet", href="style.css");
  }
  body(id="default") {
   // Page content wrapper
   div(id="wrapper", class="some_class") {
    h1 { "Hello, " + toCapital(name) + "!"; }

    // Lists post
    ul(id="post_list") {
     for(post in posts) {
      li { a(href=post.getID()) { post.tilte; } }
     }
    }
   }
  }
 }

По сути, это модифицированный источник C с удобным интерфейсом для html. Как вы можете видеть, традиционный стиль, основанный на тегах, заменяется на C-подобные команды с блоками, разделенными фигурными скобками. Мне нужно построить интерпретатор, чтобы перевести этот код в HTML и вставить его в C, чтобы он мог быть скомпилирован. Часть C остается нетронутой. Внутри источника wdi нет необходимости использовать print, каждый оператор return будет использоваться для вывода (в функции printf). Вывод программы будет чистый HTML-код.

Так, например, тег заголовка 1 будет преобразован следующим образом: 

h1 { "Hello, " + toCapital(name) + "!"; }
// would become:
printf("<h1>Hello, %s!</h1>", toCapital(name));

Моя главная цель - создать интерпретатор для перевода источника wdi в html, например:

tag(attributes) {content} => <tag attributes>content</tag>

Во-вторых, html-код, возвращаемый интерпретатором, должен быть вставлен в C-код с помощью printfs. Переменные и функции, которые встречаются внутри wdi, также должны быть отсортированы, чтобы использовать их в качестве параметров printf (случай toCapital (name) в исходном коде).

Я ищу эффективный (я хочу создать быстрый парсер) способ создания лексера и парсера для wdi. Уже попробовал flex и bison, но я не уверен, что они лучшие инструменты. Есть ли хорошие альтернативы? Каков наилучший способ создать такого переводчика? Можете ли вы посоветовать краткую литературу по этому вопросу?

Ответы [ 4 ]

3 голосов
/ 20 мая 2010

bison / flex или yacc / lex - это традиционный способ сделать это. ИМХО, нет ничего лучше подходящего для поставленной задачи.

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

Лучше сделать это правильно. Вероятнее всего, парсер, сгенерированный yacc / bison, будет намного чище (и быстрее), чем какой-то рекурсивный нисходящий парсер, созданный вручную.

1 голос
/ 22 июня 2010

Boost Spirit может быть лучше, чем бизон / флекс для таких целей.

1 голос
/ 08 июня 2010

Если вы действительно серьезно относитесь к этому, вам нужно изменить существующий синтаксический анализатор Си. Edison Design Group C Front End может быть вариантом, хотя действительно хочет быть просто интерфейсом C (C ++).

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

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

1 голос
/ 20 мая 2010

Могу ли я предложить этот учебник: http://www.icemanind.com

Там есть руководство по написанию собственной виртуальной машины, в комплекте с ассемблером и интерпретатором

...