Как я могу определить повторяющиеся элементы в CFG? - PullRequest
Новая
       6

Как я могу определить повторяющиеся элементы в CFG?

0 голосов
/ 11 апреля 2020

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

Как правильно определить идентификатор в грамматике без контекста. На данный момент у меня есть такой формат: 

IdentifierStart => $l$ | _; 
IdentifierChar => "$l$$IdentifierChar$" | "_$IdentifierChar$" | "$i$$IdentifierChar$" | $e$;
Identifier => "$IdentifierStart$$IdentifierChar$" $w$;

Формат: 

$l$ = any letter 
$e$ = epsilon
$i$ = any integer
$o$ = any operator
$n$ = new line
$w$ = whitespace
$a$ = any atom
Quotes mean the whitespace needs to match the inside of the quotes

Хотя это работает, это неэффективно, потому что создает глубокое дерево, когда каждая буква может оправданно просто быть перечислены рядом друг с другом. Например, Pragma => $n$ "#direct" $w$ $String$; с правилами: 

IdentifierStart => $l$ | _;
IdentifierChar => "$l$$IdentifierChar$" | "_$IdentifierChar$" | "$i$$IdentifierChar$" | $e$;
Identifier => "$IdentifierStart$$IdentifierChar$";

Symbol => $l$ | $i$ | $o$ | \$$Identifier$\$;
Def => $Symbol$ $Def$ | $Symbol$ | "Def";
Assignment => $Def$ \| $Assignment$ | $Def$;
Definition => $Identifier$ "=>" $Assignment$\;;

создает следующее дерево (где каждый пробел представляет уровень в дереве): 

Definition:Pragma => $n$ "#pragma" $w$ $String$;
  Identifier:Pragma
   IdentifierStart:P
    Terminal:P
   IdentifierChar:ragma
    Terminal:r
    IdentifierChar:agma
     Terminal:a
     IdentifierChar:gma
      Terminal:g
      IdentifierChar:ma
       Terminal:m
       IdentifierChar:a
        Terminal:a
  Terminal:=
  Terminal:>
  Assignment:$n$ "#direct" $w$ $String$
...

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

File => $ValidDirective$ $File$;
ValidDirective => $Comment$ | $Include$ | $Define$ | $Undef$ | $IfPart$ | $Error$ | $Pragma$ | $String$;

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

Можно ли как-нибудь исправить эту проблему, оставаясь верным соглашениям CFG?

1 Ответ

1 голос
/ 12 апреля 2020

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

Язык программирования обычно использует регулярные выражения (или что-то подобное) для определения синтаксиса символов, таких как идентификаторы , В этом случае анализ идентификатора приведет к одному токену, а не к дереву, что может ответить на ваши опасения по поводу неэффективности.

Однако этот подход не применим к повторяющимся конструкциям более высокого уровня, например StatementList или ArgumentList: для этого регулярных выражений недостаточно, и вам нужно что-то настолько же мощное, как CFG. Неясно, считаете ли вы, что сохранение StatementList или ArgumentList в виде глубоко вложенного дерева неэффективно.

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

Большинство грамматик языка программирования не ограничиваются чистый CFG, хотя.

...