かぎ針編みの英文パターンを構文解析してみた

## はじめに
編み物の経験がある方はご存じかもしれませんが編み物には編み図と呼ばれる設計図があり、日本では編み図によって作り方の記録や共有がなされています。一方、海外では文章で作り方を記すことが一般的です。
これはかぎ針編みの手順を表したものですが、編み図を読むことに慣れた日本人にとって英語で書かれた文章パターンは直感的に理解しがたく、取り組みにくいものとなっています。その一方でプログラミングに似た規則性を持っています。おそらくプログラムを書くことが好きな人ならこの文章パターンもプログラムを読むかの如く楽しく読めることでしょう。
かぎ針編みのパターンをDSL(ドメイン固有言語)として捉え、構文解析を使って読み解き、編み図生成を行うことができれば、限られた人しか扱えなかったパターンをより多くの人に身近に感じてもらえるのではないかと考え、まずはBNF記法にすることでパターンの理解を深めました。というのが前回の記事です。今回は作成したBNF記法をもとにLarkというpythonライブラリを用いて英文パターンをパーシングしてみました。

## 構文解析(Parsing) 
ある入力に対し、思い通りの挙動をさせることを目的として、入力を意味のある構造(ASL)に変換させることです。これにより機械的な処理や可視化が可能となります。

## Lark
Larkはパーシングのためのpythonライブラリです。EBNF記法に基づいて文法を定義することで自動的にASLを構築し、パーサーを作成してくれます。

## Larkを用いたパーサーの作成
まずはLarkを用いて文法を定義し、パーサーを作成してみます。
ここで前回作成したBNF記法で表したかぎ針編みの英文パターンを載せておきます。

~~~
<header>       ::= "R" | "Row" | "ROUND" | "ROW"
<split>		   ::= " " | "," | "+"
<end>		   ::= "." 
<all_col>      ::=  "[" <number> "]" | "(" <number> ")" | "<" <number> ">"  
<number>       ::= <digit>+
<digit>        ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<stitch_kind>  ::= "ch" | "sc" | "dc" | "tr" | "hdc" | "inc" | "dec"
                | "CH" | "SC" | "DC" | "TR" | "HDC" | "INC" | "DEC"
<special>      ::= "sl st" | "Fasten off" | "close ring" | " in MR"
<stitch>       ::= <stitch_kind> | <stitch_kind>  " "*  <number> | <number> " "*  <stitch_kind> 
<repeat>       ::= "(" <operations> ")" <split>*   "x" <number> 
<operations>   ::= <stitch> | <stitch> <split>* <operations> | <repeat>
<pattern>      ::= <header> <split>*  <number> <split>* ":" <split>*  <operations>  <split>* (<special> <split>*)* <end>* <all_col>?
~~~
これをLarkが読める文法に書き換えます。
といっても<>の削除と::=を:に変更するだけでした。数字やスペースの定義はLarkで提供されているので利用しました。
~~~
grammer=
'''
header       : "R" | "Row" | "ROUND" | "ROW"
split		   : " " | ","
end		   : "." 
all_col      :  "[" number "]" | "(" number ")" | "<" number ">"  
?number       : SIGNED_NUMBER
!?stitch_kind  : "ch" | "sc" | "dc" | "tr" | "hdc" | "inc" | "dec"
                | "CH" | "SC" | "DC" | "TR" | "HDC" | "INC" | "DEC"
special      : "sl st" | "Fasten off" | "close ring" | " in MR"
stitch       : stitch_kind | stitch_kind " "* number | number " "* stitch_kind 
repeat       : "(" operations ")" split*   "x" " "* number 
operations   : (( stitch | repeat )  split* )+
head_number : header split*  number
start      : head_number split* ":" split*  operations  split* special* split* end* all_col?

%import common.SIGNED_NUMBER
'''
~~~
文法を定義したらパーサーを作成します。
~~~
import logging
from lark import Lark, logger
logger.setLevel(logging.WARN)
parser= Lark(grammer2, ambiguity="explicit")
~~~
こんな感じで木構造に変換することができます。
~~~
test1='R1:(9SC,2DEC,SC3) x6[18]'
test1_p=parser.parse(test1)
print(test1_p.pretty())
~~~
~~~
start
  row
    head_number
      header
      1
    operations
      repeat
        operations
          stitch
            9
            SC
          split
          stitch
            2
            DEC
          split
          stitch
            SC
            3
        split
        6
    all_col	18
~~~
得られた木構造から必要な情報だけを抽出します。
~~~
from lark import Transformer, Token, Tree

class MyTransformer(Transformer):
    def head_number(self, items):
        return dict(header=items[1][0])
    def stitch(self,items):
        if len(items)==1:
            return dict(kind = items[0].value, times = 1)
        if len(items)==2 and items[0].type != "SIGNED_NUMBER":
            return dict(kind = items[0].value, times = items[1].value)
        else:
            return dict(kind = items[1].value,times = items[0].value)
    def operations(self,items):
        return [item for item in items if not self._is_split(item)]
    def repeat(self,items):
        op, num = [item for item in items if not self._is_split(item)]
        return dict(operation = op,times = num.value)
    def start(self,items):
        head, ope = [item for item in items if isinstance(item,list) or isinstance(item,dict)]
        return head,ope
    
    def _is_split(self,tree):
        if not isinstance(tree,Tree):
            return False
        return tree.data.value=='split'
print(MyTransformer().transform(test1_p))      
~~~
とてもいい感じに抽出できました。
~~~
({'header': '1'}, [{'operation': [{'kind': 'SC', 'times': '9'}, {'kind': 'DEC', 'times': '2'}, {'kind': 'SC', 'times': '3'}], 'times': '6'}])
~~~
これをもとに編み図に起こそうと思いましたが力尽きました。後日頑張ります！


~~~
## 参考
https://lark-parser.readthedocs.io/en/stable/