Есть ли исследования разбора в двух измерениях?

Question

В теории формального языка язык L над алфавитом Σ является подмножеством Σ* (набора слов над этим алфавитом). Для таких (одномерных) языков было проведено множество исследований эффективных методов синтаксического анализа (например, LL(K), LR(K), GLR, Earley и т. Д.).

Для каждого такого L мы можем определить соответствующий двумерный язык L_{2D для} того же алфавита, что и пара (L, w), где w: L → ℕ - функция ширины, а под L_2D понимаются те же слова. начиная с L, за исключением того, что слова могут иметь символ новой строки n_ℓ ∉ Σ, произвольно перемеженный. Есть ли теоретическая работа по эффективному и систематическому анализу таких двумерных языков? Каково современное состояние в этой области? Или есть какой-то способ перевести эту проблему в проблему разбора другого одномерного языка?

Одним из мест, где это может быть полезно, является систематический анализ структурированных двумерных текстовых данных. Например, Markdeep использует специальный анализ для преобразования простых текстовых диаграмм в SVG. Вместо этого, если бы был структурированный способ сделать это, можно было бы написать составные парсеры. Вот пример с псевдокодом:

// '.' means extend from left, ',' means extend from above
text_box = Matcher2D("
    +-.+
    |a.|
    ,,,,
    +-.+
");
s = "
+----+
|foox|   +---+    +--+
|quzy|   |bar|   |nope|
+----+   +---+    +--+
"
assert(count_matches(text_box, s) == 2)

Answer 1

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

Например, Стефано Креспи Региззи и Маттео Праделла в своей статье CKY-синтаксический анализатор для графических грамматик представил некоторые работы по анализу контекстно-свободных версий этих языков.

В любом случае, вероятно, https://cstheory.stackexchange.com/ - лучшее место, чтобы задать этот вопрос.