LoginSignup
1
0
@ikuo0

JSONパーサー作る（逆ポーランド記法を使用）

Last updated at Posted at 2024-05-20

※※※
JSONのパースに逆ポーランド記法を用いるのは一般的ではないと思います
実験的にやってみたというだけですので「JSONパースは逆ポーランド記法でやる」という誤った認識にならないようお願いします
※※※

JSONパーサーを逆ポーランド記法を使用して作成する

JSONのパーサーを作成します

  • 構文解析
  • 逆ポーランド記法へ変換
  • 逆ポーランド記法からJSONデータを作成

この順番で実行していきます

前回逆ポーランド記法を作成してみたのですが、逆ポーランド記法はJSONパースにも使えるのでは？と思ったので実装してみました
前回の記事

設計

基本的には中置記法を逆ポーランド記法にするロジックを使いまわします
配列（[]）、辞書型（{}）については関数として扱います

中置記法を逆ポーランド記法のロジックそのままで作成すると、配列と辞書型は順序を保つのが困難だったり、要素数が０個～１個の時に解析不能となったりするので [], {} が現れた時は「配列を作成する関数である」と解釈して作成します

配列の処理

[1, 2, 3, 4]
という配列は逆ポーランド記法で記載し
1 2 3 4 4 []
という表現とします
1 2 3 4 4　がスタックされ　[]　が出現すると配列を作成する関数と解釈し
スタックからpopした値を配列数と解釈、stackから配列数分を取得し配列の内容とします

辞書型も同様とし
key1 value1 key2 value2 key3 value3 ...
と並べます

１．構文解析

まずは構文解析をします
数字なら NUMBER とか、カンマなら VALUE_SEPARATOR のようにトークンを定義します、言語作成入門によく出てくる lex とか flex みたいな事をします

1 + 1 = 2

であれば NUMBER PLUS NUMBER OP NUMBER みたいにそのトークンの役割に変換します
定義は下記ソース参照

class TokenIdDefine(enum.Enum):
  # 入力文字列と対になるトークン定義
  NOP = enum.auto()
  KEY = enum.auto()
  NUMBER = enum.auto()
  STRING = enum.auto()
  DICTIONARY = enum.auto()
  KEY_VALUE_SEPARATOR  = enum.auto()
  VALUE_SEPARATOR = enum.auto()
  BEGIN_ARRAY_BRACKET = enum.auto()
  END_ARRAY_BRACKET = enum.auto()
  BEGIN_DICTIONARY_BRACKET = enum.auto()
  END_DICTIONARY_BRACKET = enum.auto()
  
  # スタックマシン用に作成する関数定義
  ARRAY_FUNCTION = enum.auto()
  ARRAY_ARG_COUNT = enum.auto()
  DICTIONARY_FUNCTION = enum.auto()
  DICTIONARY_ARG_COUNT = enum.auto()
  ERROR = enum.auto()

解析結果

以下のJSONを構文解析します

  {
    "number": 1,
    "string": "hoge",
    "array": [1, 2, 3],
    "dictionary": {
      "item1": 999,
      "item2": "text"
    }
  }

以下のような結果になります

TokenIdDefine.NOP
TokenIdDefine.BEGIN_DICTIONARY_BRACKET
TokenIdDefine.NOP
TokenIdDefine.STRING
TokenIdDefine.KEY_VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.NUMBER
TokenIdDefine.VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.STRING
TokenIdDefine.KEY_VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.STRING
TokenIdDefine.VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.STRING
TokenIdDefine.KEY_VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.BEGIN_ARRAY_BRACKET
TokenIdDefine.NUMBER
TokenIdDefine.VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.NUMBER
TokenIdDefine.VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.NUMBER
TokenIdDefine.END_ARRAY_BRACKET
TokenIdDefine.VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.STRING
TokenIdDefine.KEY_VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.BEGIN_DICTIONARY_BRACKET
TokenIdDefine.NOP
TokenIdDefine.STRING
TokenIdDefine.KEY_VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.NUMBER
TokenIdDefine.VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.STRING
TokenIdDefine.KEY_VALUE_SEPARATOR
TokenIdDefine.NOP
TokenIdDefine.STRING
TokenIdDefine.NOP
TokenIdDefine.END_DICTIONARY_BRACKET
TokenIdDefine.NOP
TokenIdDefine.END_DICTIONARY_BRACKET
TokenIdDefine.NOP

NOPはそもそも不要なのでこの時点で削除しても良さそうですね、なんとなく残したまま最後まで作りましたが使用用途が無いので削除で良いと思います

逆ポーランド記法への変換

詳細な動作についてはページ下部にソースコード全体を掲載していますのでそちらを参照してください
infixNotationToReversePolishNotation という関数が変換関数になります

動作解説

入力配列からトークンがなくなるまで以下の動作を繰り返します

  • 入力トークン、スタックしたトークンに各々優先順位をつけてスタックするか出力するかを選択します
  • 開始括弧が現れたら要素数のスタックを作成し要素数カウントをします
  • 終了括弧が現れたらスタックの始まり括弧までの内容を出力します

逆ポーランド記法からJSONデータへの変換

詳細な動作についてはページ下部にソースコード全体を掲載していますのでそちらを参照してください
jsonRpnToData という関数が変換関数になります

動作解説

入力配列からトークン・値ペアがなくなるまで以下の動作を繰り返します

  • 配列関数だったらスタックから配列分の数だけデータを取り出し配列にしてからスタックに戻します
  • 辞書関数だったらスタックから配列分の数だけデータを取り出し配列にしてからスタックに戻します
  • 配列でも辞書でも無い場合（数字か文字）スタックします

最後までスタックに残ったデータを完成したデータとして返します

以上です

ソースコード全体

# @title

import re
import sys
import enum
import typing
import json
import dataclasses

class TokenIdDefine(enum.Enum):
  # 入力文字列と対になるトークン定義
  NOP = enum.auto()
  KEY = enum.auto()
  NUMBER = enum.auto()
  STRING = enum.auto()
  DICTIONARY = enum.auto()
  KEY_VALUE_SEPARATOR  = enum.auto()
  VALUE_SEPARATOR = enum.auto()
  BEGIN_ARRAY_BRACKET = enum.auto()
  END_ARRAY_BRACKET = enum.auto()
  BEGIN_DICTIONARY_BRACKET = enum.auto()
  END_DICTIONARY_BRACKET = enum.auto()
  
  # スタックマシン用に作成する関数定義
  ARRAY_FUNCTION = enum.auto()
  ARRAY_ARG_COUNT = enum.auto()
  DICTIONARY_FUNCTION = enum.auto()
  DICTIONARY_ARG_COUNT = enum.auto()
  ERROR = enum.auto()

@dataclasses.dataclass
class TokenValuePair:
    token: TokenIdDefine
    value: str

def indexing(array: typing.List[typing.Any], indexes: typing.List[int]):
  res = []
  for i in indexes:
    res.append(array[i])
  return res

def matchToken(tokenRules: typing.List[typing.List], infixNotation: str, index: int) -> typing.Tuple[typing.Any, int]:
  for tokenRule in tokenRules:
    regexp, token = tokenRule
    match = re.match(regexp, infixNotation[index:])
    if match != None:
      return token, match.end()
  return TokenIdDefine.ERROR, 0

def lexer(jsonString):
  tokenRules = [
      ["^[\s\n]+", TokenIdDefine.NOP],
      ["^[\d\.]+", TokenIdDefine.NUMBER],
      ["^\"[^\"]*\"", TokenIdDefine.STRING],
      ["^:", TokenIdDefine.KEY_VALUE_SEPARATOR],
      ["^,", TokenIdDefine.VALUE_SEPARATOR],
      ["^\[", TokenIdDefine.BEGIN_ARRAY_BRACKET],
      ["^\]", TokenIdDefine.END_ARRAY_BRACKET],
      ["^\{", TokenIdDefine.BEGIN_DICTIONARY_BRACKET],
      ["^\}", TokenIdDefine.END_DICTIONARY_BRACKET],
  ]
  tokens = []
  values = []
  index = 0
  while(index < len(jsonString)):
    token, size = matchToken(tokenRules=tokenRules, infixNotation=jsonString, index=index)
    if token == TokenIdDefine.ERROR or size <= 0:
      print("error on {} character".format(index))
      break
    value = jsonString[index:index + size]
    tokens.append(token)
    values.append(value)
    index += size
  return tokens, values

def printValueArray(pairs, inputValue):
    print("{} ###> {}".format(" ".join([str(x.value) for x in pairs]), inputValue))

def infixNotationToReversePolishNotation(tokens: typing.List[TokenIdDefine], values: typing.List[str]):
  tokenIdToInputPriority = {
      TokenIdDefine.NUMBER:                   10,
      TokenIdDefine.STRING:                   10,
      TokenIdDefine.BEGIN_ARRAY_BRACKET:      9,
      TokenIdDefine.END_ARRAY_BRACKET:        0,
      TokenIdDefine.BEGIN_DICTIONARY_BRACKET: 9,
      TokenIdDefine.END_DICTIONARY_BRACKET:   0,
  }
  tokenIdToStackPriority = {
      TokenIdDefine.NUMBER:                   10,
      TokenIdDefine.STRING:                   10,
      TokenIdDefine.BEGIN_ARRAY_BRACKET:      0,
      TokenIdDefine.END_ARRAY_BRACKET:        0,
      TokenIdDefine.BEGIN_DICTIONARY_BRACKET: 0,
      TokenIdDefine.END_DICTIONARY_BRACKET:   0,
  }
  output = []
  stack = []
  counterStack = []
  size = len(tokens)
  inputIndex = 0
  while(inputIndex < size):
    inputToken = tokens[inputIndex]
    inputValue = values[inputIndex]
    pairVariable = TokenValuePair(token=inputToken, value=inputValue)

    if inputToken in [TokenIdDefine.NOP, TokenIdDefine.KEY_VALUE_SEPARATOR]:
      inputIndex += 1
      continue

    if inputToken == TokenIdDefine.VALUE_SEPARATOR:
      counterStack[-1] += 1
      inputIndex += 1
      continue
    
    #printValueArray(stack, inputValue)
    if (inputToken in [TokenIdDefine.BEGIN_ARRAY_BRACKET, TokenIdDefine.BEGIN_DICTIONARY_BRACKET]) and (len(stack) == 0 or tokenIdToInputPriority[inputToken] < tokenIdToStackPriority[stack[-1].token]):
      counterStack.append(0)
    elif inputToken in [TokenIdDefine.END_ARRAY_BRACKET, TokenIdDefine.END_DICTIONARY_BRACKET]:
      poped = stack.pop()
      while poped.token not in [TokenIdDefine.BEGIN_ARRAY_BRACKET, TokenIdDefine.BEGIN_DICTIONARY_BRACKET]:
        if poped.token in [TokenIdDefine.NUMBER, TokenIdDefine.STRING]:
          counterStack[-1] += 1
        output.append(poped)
        poped = stack.pop()
      if inputToken == TokenIdDefine.END_ARRAY_BRACKET:
        output.append(TokenValuePair(token=TokenIdDefine.ARRAY_ARG_COUNT, value=str(counterStack.pop())))
        output.append(TokenValuePair(token=TokenIdDefine.ARRAY_FUNCTION, value="[]"))
      else:
        output.append(TokenValuePair(token=TokenIdDefine.DICTIONARY_ARG_COUNT, value=str(counterStack.pop())))
        output.append(TokenValuePair(token=TokenIdDefine.DICTIONARY_FUNCTION, value="{}"))
      inputIndex += 1
      continue
    
    if len(stack) == 0 or tokenIdToInputPriority[inputToken] > tokenIdToStackPriority[stack[-1].token]:
      stack.append(pairVariable)
      inputIndex += 1
    else:
      poped = stack.pop()
      output.append(poped)
  output.extend(list(reversed(stack)))
  return output

def jsonRpnToData(jsonRpn):
  size = len(jsonRpn)
  index = 0
  stack = []

  while(index < size):
    inputPair = jsonRpn[index]
    token = inputPair.token
    value = inputPair.value
    if token == TokenIdDefine.ARRAY_FUNCTION:
      argCount = stack.pop()
      if argCount > 0:
        array = stack[-argCount:]
        stack = stack[:-argCount]
        stack.append(array)
      else:
        stack.append([])
    elif token == TokenIdDefine.DICTIONARY_FUNCTION:
      argCount = stack.pop()
      if argCount > 0:
        elementCount = argCount * 2
        dictionary = {}
        for i in range(elementCount, 0, -2):
          dictionary[stack[-i]] = stack[-i + 1]
        stack = stack[:-elementCount]
        stack.append(dictionary)
      else:
        stack.append({})
    else:
      if token in [TokenIdDefine.NUMBER, TokenIdDefine.ARRAY_ARG_COUNT, TokenIdDefine.DICTIONARY_ARG_COUNT]:
        if "." in value:
          stack.append(float(value))
        else:
          stack.append(int(value))
      else:
        stack.append(str(value).strip('"'))
    index += 1
  return stack[0]

def test2():
  jsonString1 = '''
  {
      "name": "John",
      "age": 30,
      "children": [
          {
              "name": "Jane",
              "age": 10
          },
          {
              "name": "Jack",
              "age": 8
          }
      ]
  }
  '''
  jsonString2 = """
  {
    "number": 999,
    "array": [9, 8, 7],
    "ppp": [1, {"a": "b", "x": 666}, 777],
    "string": "hogehoge"
  }
  """
  jsonString3 = """
  {
    "number": 999,
    "array": [9, 8, 7],
    "ppp": [1, {"a": "b", "x": 666}, 777],
    "array1": [0],
    "array2": [],
    "string": "hogehoge"
  }
  """
  jsonString4 = """
  [1, 2, [1, 2], 3, 4]
  """
  jsonString5 = """
  [1, 2, 3, 4]
  """
  jsonString6 = """
  {
    "number": 1,
    "string": "hoge",
    "array": [1, 2, 3],
    "dictionary": {
      "item1": 999,
      "item2": "text"
    }
  }
  """
  jsonString = jsonString6
  tokens, values = lexer(jsonString)
  print("\n".join([str(token) for token in tokens]))
  tokenValuePairs = infixNotationToReversePolishNotation(tokens, values)
  tokensString = " ".join([str(x.token) for x in tokenValuePairs])
  valuesString = " ".join([str(x.value) for x in tokenValuePairs])
  print(tokensString)
  print(valuesString)
  jsonData = jsonRpnToData(tokenValuePairs)
  print(jsonData)

def testSub(jsonString):
  tokens, values = lexer(jsonString)
  tokenValuePairs = infixNotationToReversePolishNotation(tokens, values)
  jsonData = jsonRpnToData(tokenValuePairs)
  return jsonData

def test1():
  print(testSub("1234"))
  print(testSub('"hoge"'))
  print(testSub('[1, 2, 3, 4]'))
  print(testSub('["a", "b", "c", "d"]'))
  print(testSub('[1, "b", 3, "d"]'))
  jsonString = """
  {
    "number": 999,
    "array": [9, 8, 7],
    "ppp": [1, {"a": "b", "x": 666}, 777],
    "array1": [0],
    "array2": [],
    "string": "hogehoge"
  }
  """
  print(testSub(jsonString))

if __name__ == "__main__":
  #test1()
  test2()
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0