【スマートスピーカー】家電操作命令の構文解析【Python】

# 概要
スマートスピーカーへの実装を想定した家電操作命令の構文解析器をつくりました。
特に「リビングのエアコンと電気を消して」などのような複数の家電をまとめて操作する命令を解釈することを目指しました。
# 背景
スマートスピーカを使っていると複数の家電をまとめて操作したくなることがあります。複数の家電をまとめて操作するための機能として定形アクションがありますが、事前登録が必要なため、急な需要には対応できません。定形アクションが登録されていない場合には「リビングのエアコン消して」「リビングの電気を消して」などと家電ごとに順に操作を実行させる必要があり、時間がかかります。もし「リビングのエアコンと電気を消して」などのように一文でスマートスピーカに認識させることができれば、時間の節約になります。そこで、本記事では構文解析によって**複数家電を同時に操作するための命令を解釈**するプログラムを作ることを目指します。
# テストケースの作成
家電操作命令が「部屋」「機器」「操作」および「助詞」からなる系列であるという前提で、スマートスピーカに言いそうな命令を列挙しました。

```Python
class Lexer:
  # 名詞の定義
  devices = ["電気","エアコン","テレビ"]
  rooms = ["リビング","寝室","和室"]
  operations = ["つけ","消し"]
  joints = ["と","の","を","て"]

  def exec(text):
    #あとで処理を書く
    pass

import unittest
prompt_cases = [
  ["リビング 電気 消し" # <room> <device> <operation>
    , ["リビング 電気 消し"] ]
  , ["リビング 電気 エアコン 消し" # <room> <device>+ <operation>
    , ["リビング 電気 消し", "リビング エアコン 消し"]] 
  , ["リビング 和室 電気 消し" #<room>+ <device> <operation>
    , ["リビング 電気 消し", "和室 電気 消し"]]
  , ["リビング 和室 電気 エアコン 消し" #<room>+ <device>+ <operation>
    , ["リビング 電気 消し", "リビング エアコン 消し", "和室 電気 消し", "和室 エアコン 消し"]]
  , ["リビング 電気 エアコン 消し テレビ つけ" # <room> (<device>+ <operation>)+
    , ["リビング 電気 消し", "リビング エアコン 消し", "リビング テレビ つけ"]]
  , ["リビング 電気 寝室 和室 エアコン テレビ 消し" # (<room>+ <device>+)+ <operation>
    , ["リビング 電気 消し", "寝室 エアコン 消し", "寝室 テレビ 消し", "和室 エアコン 消し", "和室 テレビ 消し"] ]
  , ["リビング 電気 消し 和室 電気 つけ" # (<room> <device> <operation>)+
    , ["リビング 電気 消し","和室 電気 つけ"]]
  , ["リビング 寝室 電気 エアコン 消し 和室 電気 つけ エアコン 消し" # ( ( (<room>+ <device>+)+ <operation> ) | (<room>+ (<device>+ <operation>)+ ) )+
    , ["リビング 電気 消し", "リビング エアコン 消し", "寝室 電気 消し", "寝室 エアコン 消し", "和室 電気 つけ", "和室 エアコン 消し"]]
  , ["リビング の 電気 と エアコン を 消し て" # with joints
    , ["リビング 電気 消し", "リビング エアコン 消し"] ]

  ]
lexer = Lexer()
class TestPrompt(unittest.TestCase):
  def test_exec(self):
    for arg, result in prompt_cases:
      self.assertCountEqual(lexer.exec(arg), result) #要素の数え上げで比較することで順番を無視
```

入出力について、今回は「複雑な」家電操作命令を、「部屋」「家電」「操作」１つずつからなる「単純な」操作命令に変換（出力）できればOKとします。テストケースはありそうなパターンを想像して書いています。完全に網羅できているかはわかりません。

# バッカスナウア記法（BNF）による入力の表現
構文解析の方針をたてるため、入力をバッカスナウア記法（BNF）の式で定義します。
テストケースの家電操作命令を眺めると

1. 「部屋と家電」のセットに対して「操作」をくっつけるパターン（例：リビングの電気と和室のエアコンをつけて）
1. 部屋」に対して「家電と操作」のセットをくっつけるパターン（例：リビングの電気をつけてエアコンを消して）
1. 1と2どちらともみなせるもの（例：リビングの電気とエアコンを付けて）
1. 1または2をつなげたもの（例：リビングの電気をつけて和室のエアコンを消して）

というパターンが有ることがわかります。
3は1または2の式で解釈可能なため無視できます。4は1と2が定義できれば再帰で表現可能です。
したがって、\<prompt\>を入力、\<room\>、\<device\>、\<operation\>を最小単位のトークンとしたとき、以下のような式となります。

```
<prompt> ::= (<roomdevice> <operation>) | (<room>+ <deviceoperation>) [<prompt>]  
<roomdevice> ::= <room>+ <device>+ [<roomdevice>]
<deviceoperation> ::= <device>+ <operation> [<deviceoperation>]
```

\+は1回以上の繰り返し、\[\]は0または1回登場することを意味します。\<prompt\>の定義に\<prompt\>を用いているので再帰的に構文を解析することができます。\<roomdevice\>、\<deviceoperation\>はそれぞれ「部屋と家電」、「家電と操作」に対応する項目です。テストケースからどちらも複数回繰り返し登場させられることがわかるので、これらも再帰的な式となっています。また各式において\<room\>、\<device\>は複数回繋げられるので\+をつけています。対して\<operation\>は繋げられない（「つけてけして」のような構成は今回は認めない）ので、\+がついていません。

# 実装
BNFに沿って構文解析器を実装します。

```Python
"""
<prompt> ::= (<roomdevice> <operation>) | (<room>+ <deviceoperation>) [<prompt>]  
<roomdevice> ::= <room>+ <device>+ [<roomdevice>]
<deviceoperation> ::= <device>+ <operation> [<deviceoperation>]
"""

class Lexer:
  # 名詞の定義
  devices = ["電気","エアコン","テレビ"]
  rooms = ["リビング","寝室","和室"]
  operations = ["つけ","消し"]
  joints = ["と","の","を","て"]

  def __init__(self):
    pass  
  def is_room(self,token):
    return token in self.rooms
  def is_device(self,token):
    return token in self.devices
  def is_operation(self,token):
    return token in self.operations
  def remove_joints(self,tokens):
    return [v for v in tokens if v not in self.joints]

  #roomとdeviceの組み合わせを取得する
  def roomdevice(self,tokens):

    # tokensの長さが0だったり、先頭がroom出ない場合、空のリストを返す（再帰を終了する）
    if len(tokens) == 0:
      return [], 0
    if not self.is_room(tokens[0]):
      return [], 0
    
    orders, rooms, devices = [],[],[]

    # 先頭から連続するroomをすべて取得
    cnt = 0
    while cnt < len(tokens):
      if self.is_room(tokens[cnt]):
        rooms.append(tokens[cnt])
        cnt+=1
      else:
        break
    # 文法上の要請から（連続する）roomのつぎはdeviceが来る必要がある
    assert self.is_device(tokens[cnt])

    # 連続するdeviceをすべて取得する
    while cnt < len(tokens):
      if self.is_device(tokens[cnt]):
        devices.append(tokens[cnt])
        cnt += 1
      else:
        break
    
    # roomとdeviceの組み合わせをすべて取得
    for room in rooms:
      for device in devices:
        orders.append([room, device])
    
    # 最初のroom、device以降について再帰的に解析
    next_orders, length = self.roomdevice(tokens[len(rooms)+len(devices):])
    # 上位の関数(prompt）が使うため、解析済みの長さを合わせて返す
    return orders + next_orders, len(rooms)+len(devices)+length

  # deviceとoperationの組み合わせをparseする
  def deviceoperation(self,tokens):
    # リストが空のとき、または、先頭がdeviceでないとき再帰を終了する
    if len(tokens) == 0:
      return [],0
    if not self.is_device(tokens[0]):
      return [],0
    

    orders = []
    devices, operations = [], ""

    # 先頭から連続するdeviceをすべて取得
    cnt = 0
    while cnt < len(tokens):
      if self.is_device(tokens[cnt]):
        devices.append(tokens[cnt])
        cnt += 1
      else:
        break

    # 連続するdeviceの次はoperationである必要がある
    assert self.is_operation(tokens[cnt])
    # operationは連続しないはずなので、1つだけ取得
    operation = tokens[cnt]

    # deviceとoperationの組み合わせを作る
    for device in devices:
      orders.append([device, operation])

    # operationより後ろの部分について再帰的に解析する
    next_orders, length = self.deviceoperation(tokens[len(devices)+1:])
    # 上位の関数（prompt）が使うため、解析が完了した部分の長さを合わせて返す
    return orders + next_orders, len(devices)+1+length

  # 入力をparseする
  def prompt(self,tokens):
    # 空のとき再帰を終了する
    if len(tokens) == 0:
      return [], 0
    # 文法規則上、先頭はroomである必要がある
    assert self.is_room(tokens[0])
    # "<roomdevice> <operation>"パターンか"<room>+ <deviceoperation>"パターンかの判定
    # 冒頭が<room>+ <device>+ <room> という並びであれば"<roomdevice> <operation>"パターン
    # それ以外は"<room>+ <deviceoperation>"パターン

    # とりあえずroom+ device+の部分を取得
    room_cnt, device_cnt = 0, 0
    while room_cnt<len(tokens):
      if self.is_room(tokens[room_cnt]):
        room_cnt += 1
      else:
        break
    assert self.is_device(tokens[room_cnt])
    while room_cnt+device_cnt < len(tokens):
      if self.is_device(tokens[room_cnt+device_cnt]):
        device_cnt += 1
      else:
        break
    
    orders, length = [], 0
    assert room_cnt+device_cnt < len(tokens), tokens
    assert self.is_room(tokens[room_cnt+device_cnt]) or self.is_operation(tokens[room_cnt+device_cnt]), tokens[room_cnt+device_cnt]
    # room+ device+ roomのとき、<roomdevice> <operation>とみなす
    if self.is_room(tokens[room_cnt+device_cnt]):
      roomdevices, roomdevicelength = self.roomdevice(tokens)
      assert self.is_operation(tokens[roomdevicelength]), "{}, {}".format(tokens, length)
      operation = tokens[roomdevicelength]
      for rd in roomdevices:
        orders.append(rd + [operation])
      length = roomdevicelength+1 #operationの長さ(1)を足す
    # room+ device+ operationのとき、<room>+ <deviceoperation>とみなす
    elif self.is_operation(tokens[room_cnt+device_cnt]):
      rooms = tokens[:room_cnt]
      deviceoperations,deviceoperationlength = self.deviceoperation(tokens[room_cnt:])
      for room in rooms:
        for do in deviceoperations:
          orders.append([room]+do)
      length = room_cnt+deviceoperationlength
    
    # 最初の塊より後ろを再帰的に解析する
    next_orders, next_length = self.prompt(tokens[length:])
    return orders+next_orders, length+next_length
  def exec(self,text):
    tokens = self.remove_joints(text.split()) #入力をspaceで分割して助詞を除く
    orders, _ = self.prompt(tokens)
    return [" ".join(v) for v in orders] # 各単純命令をスペースで結合して返す
```

# テスト

```Python
if __name__ == '__main__':
  unittest.main(argv=['first-arg-is-ignored'], exit=False) # notebookで実行の場合
  #unittest.main() # scriptで実行の場合
```

```
.
----------------------------------------------------------------------
Ran 1 test in 0.003s

OK
```

# おわりに
いつかこれをスマートスピーカーと組み合わせて、便利な音声操作ライフをおくりたいです。