Разобрать блок, где каждая строка начинается с определенного символа

Язык вложенных блоков не является контекстно-свободным [Примечание 2], поэтому его нельзя проанализировать с помощью синтаксического анализатора LALR(k).

Однако языки со вложенными скобками, конечно же, не зависят от контекста, и относительно легко преобразовать ввод в форму скобок, заменив начальные последовательности | в лексическом сканере. Трансформация проста:

• когда исходная последовательность | длиннее предыдущей строки, вставьте BEGIN_BLOCK. (Исходная последовательность должна быть ровно на один | длиннее, иначе это предположительно синтаксическая ошибка.)

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

• Сами | не передаются парсеру.

Это очень похоже на стратегию INDENT/DEDENT, используемую для синтаксического анализа языков с поддержкой макета, таких как Python и Haskell. Главное отличие в том, что здесь нам не нужен стек уровней отступов.

Как только это преобразование будет завершено, грамматика будет выглядеть примерно так:

content: /* empty */
       | content line
       | content block
block  : head BEGIN_BLOCK content END_BLOCK
       | head
head   : '*' line

Грубый план гибкой реализации будет примерно таким: (см. примечание 1 ниже).

%x INDENT CONTENT
%%
  static int depth = 0, new_depth = 0;
  /* Handle pending END_BLOCKs */
  send_end:
    if (new_depth < depth) {
      --depth;
      return END_BLOCK;
  }
^"|"[[:blank:]]*   { new_depth = 1; BEGIN(INDENT); }
^.                 { new_depth = 0; yyless(0); BEGIN(CONTENT);
                     goto send_end; }
^\n                /* Ignore blank lines */
<INDENT>{
  "|"[[:blank:]]*  ++new_depth;
  .                { yyless(0); BEGIN(CONTENT);
                     if (new_depth > depth) {
                       ++depth;
                       if (new_depth > depth) { /* Report syntax error */ }
                       return BEGIN_BLOCK;
                     } else goto send_end;
                   }
  \n               BEGIN(INITIAL); /* Maybe you care about this blank line? */
}
  /* Put whatever you use here to lexically scan the lines */
<CONTENT>{
  \n               BEGIN(INITIAL);
}

Заметки:

1. Не всем понравится goto, но он избавляет от дублирования кода. Тот факт, что переменные состояния (depth и new_depth) являются локальными переменными static, делает лексер нереентерабельным и не перезапускаемым (после ошибки). Это полезно только для игрушечного кода; для чего-либо реального вы должны сделать лексический сканер реентерабельным и поместить переменные состояния в структуру данных extra.

2. Термины «контекстно-независимый» и «контекстно-зависимый» являются техническими описаниями грамматик и поэтому немного вводят в заблуждение. Интуиция, основанная на том, что слова кажутся означающими, часто ошибочна. Одним из очень распространенных источников контекстной зависимости является язык, в котором достоверность зависит от двух разных производных одного и того же нетерминала, создающих одну и ту же последовательность токенов. (Предположим, что нетерминал может получить более одной последовательности токенов; в противном случае нетерминал можно исключить.)

   Есть много примеров такой контекстной зависимости в обычных языках программирования; обычно грамматика разрешает эти конструкции, и проверка выполняется позже на каком-либо этапе семантического анализа. К ним относятся требование, чтобы идентификатор был объявлен (два производных от IDENTIFIER дают одну и ту же строку) или требование, чтобы функция вызывалась с правильным числом параметров (здесь необходимо только, чтобы длина производных не- терминалы совпадают, но этого достаточно, чтобы вызвать контекстную зависимость).

   В этом случае требуется, чтобы два экземпляра того, что можно было бы назвать bar-prefix в последовательных строках, давали одну и ту же строку |s. В этом случае, поскольку эффект действительно синтаксический, обращение к более позднему семантическому анализу лишает смысла синтаксический анализ. Являются ли другие примеры контекстно-зависимой «синтаксической» или «семантической» дискуссия, которая вызывает удивительное количество жара, но не проливает много света на дискуссию.

Этот ответ на самом деле является комментарием (... мой комментарий трудно прочитать)

Если вы напишите явный токен конца блока, все станет яснее.

*Block{
  |Line 1
  *SubBlock{
     | line 1.1
     | line 1.2
  }
  |Line 2
  |...
}

и грамматика становится

block : '*' ID '{' lines '}'
lines : lines  '|' line
      | lines  block
      |