⛓️

Excelの計算式を構文解析して依存関係を可視化した話

2024/07/14に公開

Excel

今回実装したものたち

動機

研究室の引き継ぎでExcelのブックをいただいたのですが、あまりに計算が複雑なため、そのまま読むのが憚られました。
このような課題は自分に限らずだれもが遭遇しうるものだと思うので、Excelのセル同士の依存関係を可視化するツールを作ろうと思い至りました。
特にこの記事の最終的な成果物として、

セル同士の依存関係が一目でわかる
各セルに名前付けができる
定数セルの値を変えた時に、結果セル計算結果がどのように変化するか確かめられる

を想定します。

まずは単純な実装(Python)

最も簡単な実装は正規表現を使うことです。例えば

\b[A-Z]+[1-9][0-9]*(?::[A-Z]+[1-9][0-9]*)?\b

このような正規表現を考えると、A1, A2:A3のようなセル表現のパターンだけを抜き出すことができます。なお、ここでは単純化のためSheet1!A3のような他のシートを参照するケースや、A:Aのような列をすべて指定するケースなどは考えていません。

なので、アルゴリズムを簡単に書くと

このようになります。

実装

実装のうち本質的な部分のみを抜き出すとこのようになります。

# セルアドレスをrootとして依存関係を計算
def get_value_or_function(workbook: "Workbook", root_cell_address: str) -> (str, str):
    sheet: Worksheet = workbook.active
    cell = sheet[root_cell_address]

    if cell.data_type == "f":
        root_cell = Cell(sheet_name="temp", address=root_cell_address, value=None)
        # Cell is function cell
        formula = cell.value
        parent_addresses = extract_cells_from_formula(formula)
        parent_addresses = unique_elements_preserve_order(parent_addresses)
        cur = DependencyTree(root_cell)
        for parent_address in parent_addresses:
            parent = get_value_or_function(workbook, parent_address)
            cur.add_dependency(parent)
        return cur
    else:
        # Cell is number cell
        root_cell = Cell(sheet_name="temp", address=root_cell_address, value=cell.value)
        return DependencyTree(root_cell)

def calc_dependency_graph(root: "DependencyTree") -> Network:
    # 有向グラフを作成
    g = nx.DiGraph()
    add_dependency_to_graph(root, g)
    net = Network(directed=True)
    net.from_nx(g)
    return net

基本的にやっていることは

セルの関数からセルアドレスの一覧を取得
それぞれに対して、再起的に1.を実行

ということで、そこまで難しいことはやっていません。
なお、Excelファイルの読み込みとしてopenpyxl、グラフの作成と可視化にnetworkxとpyvisを使いました。

結果

このようなExcelのブックに対して実行すると、

このように可視化することができました。
確かに依存関係が正しくグラフとして表せていそうです。

しかしまだ課題が

ですが、この可視化にはいくつか問題があります。

各ノードが何を表す値なのかがわからない。
ノード同士に依存関係があることはわかるが、具体的に依存元の値が変わると結果がどうなるのかがわからない。

これらを解決するため、今度は別のアプローチを取ることにしました。

今回作ったもの

まずは結論として出来上がった成果物を先に提示します。

1. Webアプリとして実装されており、ページを開くとこのような画面が表示される。

2. ファイルをアップロードすると、ファイル名が表示される。

3. 解析するシート名とセルのアドレスを入力する。

4. 「次へ」を押すとこのような画面に遷移する。

5. 数値セルの部分の値は自分で編集できるようになっており、編集後に「再計算」を押すと、新しい値に対して計算がされる。

6. 「表示名」と書かれたフィールドはユーザーが自由に編集することができる。

要件

今回作るツールの要件として、以下のように定義しました。

依存関係がUIで直感的にわかる
各セルにラベル付けをすることができる
定数セルを変更した際の計算結果を計算できる

制約

問題を簡単にするため、ここでは制約をいくつか課しています。

他のシートへの参照は許可しない
Excelの関数は四則演算に加え、SUM, AVERAGE, ROUNDのみサポートする
Excelの関数に範囲参照(A1:C3のような形式)を含めたものはサポートしない。
セルの計算結果は数値のみに限る。すなわち、BOOLなどはサポートしない。

これらは今後実装することは可能ではありますが、とりあえず基本的な機能の部分のみを作っていきます。

実装方針

方針の検討

定数セルの値を変えながら結果を観察する方法としては、

Excelの該当セルに新しい値を入れて、一度保存する
計算式を解析する

の2つの方法が考えられます。
今回は知的好奇心のために2.の方法を取りましたが、一応ソフトウェアとしてこちらの方針を取ることのメリットも考察します。

まず2つの方法を比較した際、1つ目の方法はロマンがない上に処理時間が長くなるというデメリットが考えられ、2つ目の方法は実装が大変というデメリットがあります。
今後、ある定数セルを変更した際の結果を勝手にグラフにしてくれるような機能もつけたいという展望があったため、計算時間の長さを重く見て2.の方針で実装することとしました。

具体的な実装

1. 関数文字列をトークンに分割(トークナイザーの作成)

トークンとは言語を分割した単語のことで、例えば数式が

(A1 + A2) * B1

このように表せる場合、トークン列は

"(", "A1", "+", "A2", ")", "*", "B1"

このように表されます。
今回の要件の範囲では、Excelのトークンは基本的に(, ), ,, 四則演算で分けば十分なため、以下のようにして書けます。

import { isNumeric } from "@/utils"

export type Token =
  | {
      // 記号
      kind: "RESERVED"
      expr: string
    }
  | {
      // 数値リテラル
      kind: "NUM"
      value: number
    }

const splitLetters = new Set(["(", ",", ")", "+", "-", "*", "/"])

export function tokenizer(str: string): Token[] {
  if (str[0] === "=") {
    const tokens: Token[] = []
    let token = ""
    for (let i = 1; i < str.length; i++) {
      const char = str[i]!
      if (str[i] === " ") {
        // スペースはスキップ
        continue
      }
      if (splitLetters.has(char)) {
        if (token !== "") {
          if (isNumeric(token)) {
            tokens.push({ kind: "NUM", value: Number(token) })
          } else {
            tokens.push({ kind: "RESERVED", expr: token })
          }
        }
        token = ""
        tokens.push({ kind: "RESERVED", expr: char })
        continue
      }
      token += char
    }
    // 最後に余った文字をtokensに追加
    if (token !== "") {
      if (isNumeric(token)) {
        tokens.push({ kind: "NUM", value: Number(token) })
      } else {
        tokens.push({ kind: "RESERVED", expr: token })
      }
    }
    return tokens
  }
  if (!isNumeric(str)) {
    throw new Error("Provided string is neither formula nor number.")
  }
  return [{ kind: "NUM", value: Number(str) }]
}

2. EBNFによる生成規則の記述

まずExcel関数の文法をEBNFによって記述していきます。
EBNFとは、ある言語の規則を正規表現チックに表現したものと思っていただけたらいいと思います。

まず基本的な算術演算のみをサポートする言語の場合は

expr    = mul ("+" mul | "-" mul)*
mul     = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

このように書けます。これは低レイヤを知りたい人のためのCコンパイラ作成入門の途中の内容をそのまま写しています。

ここにExcel関数を追加したものを自分で次のように定義しました。

expr       = add | cell
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-")? primary
primary    = num | funcName "(" args ")" | "(" expr ")" | cell
args       = (expr | range) ("," (expr | range)*
cell       = [A-Za-z]+ num
range      = cell ":" cell
num        = [0-9]+

3. EBNFの各項を関数として実装

EBNFが定義できれば、あとはそれぞれの項(上で言うとexpr, add, mul, unary, ...)に対応するparse関数を機械的に定義することで、parserを作ることができます。

export class Parser {
  private position: number = 0
  constructor(
    private rootAddress: string,
    private getFormula: (address: string) => string,
    /**
     * 基本的に外部から与えたtokensで初期化しない。
     * テストのために一応可能としている
     */
    private tokens: Token[] = []
  ) {}

  private static createNumberNode(
    value: number,
    cellAddress: string | undefined
  ): SyntaxTreeNode {
    return new SyntaxTreeNode("LITERAL", [], value, undefined, cellAddress)
  }

  /**
   * positionが指すtokenが数値の場合trueを返す。
   * @returns
   */
  private isCurNumber(): boolean {
    const token = this.tokens[this.position]
    if (token === undefined) {
      return false
    }
    return token.kind === "NUM"
  }

  /**
   * positionが指すtokenが想定した記号であった場合、tokenを1つ読み進めてtrueを返す。
   * それ以外の場合、falseを返す。
   * @param expected
   */
  private consume(expected: string): boolean {
    const token = this.tokens[this.position]
    if (token === undefined) {
      return false
    }
    if (token.kind !== "RESERVED" || token.expr !== expected) {
      return false
    }
    this.position++
    return true
  }

  private consumeFuncName(): string | undefined {
    const token = this.tokens[this.position]
    if (token === undefined) {
      return undefined
    }
    if (
      token.kind !== "RESERVED" ||
      !excelFuncNames.has(token.expr as ExcelFuncName)
    ) {
      return undefined
    }
    this.position++
    return token.expr
  }

  /**
   * positionが指すtokenが想定した記号であった場合、tokenを1つ読み進める。
   * それ以外の場合、エラーを返す。
   * @param expected
   */
  private expect(expected: string): void {
    const token = this.tokens[this.position]
    if (token === undefined) {
      throw new Error(`Expected ${expected}, but got EOF.`)
    }
    if (token.kind === "NUM") {
      throw new Error(`Expected ${expected}, but got ${token.value}`)
    }
    if (token.expr !== expected) {
      throw new Error(`Expected ${expected}, but got ${token.expr}`)
    }
    this.position++
    return
  }

  private expectNumber(): number {
    const token = this.tokens[this.position]
    if (token === undefined) {
      throw new Error(`Expected number, but got EOF.`)
    }
    if (token.kind === "RESERVED") {
      throw new Error(`Expected number, but got ${token.expr}`)
    }
    this.position++
    return token.value
  }

  private expectReserved(): string {
    const token = this.tokens[this.position]
    if (token === undefined) {
      throw new Error(`Expected number, but got EOF.`)
    }
    if (token.kind === "NUM") {
      throw new Error(`Expected number, but got ${token.value}`)
    }
    this.position++
    return token.expr
  }

  private expr(): SyntaxTreeNode {
    return this.add()
  }

  private add(): SyntaxTreeNode {
    let node = this.mul()
    // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition, no-constant-condition
    while (true) {
      if (this.consume("+")) {
        node = new SyntaxTreeNode(
          "ADD",
          [node, this.mul()],
          undefined,
          undefined,
          undefined
        )
      } else if (this.consume("-")) {
        node = new SyntaxTreeNode(
          "SUB",
          [node, this.mul()],
          undefined,
          undefined,
          undefined
        )
      } else {
        return node
      }
    }
  }

  private mul(): SyntaxTreeNode {
    let node: SyntaxTreeNode = this.unary()

    // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition, no-constant-condition
    while (true) {
      if (this.consume("*")) {
        node = new SyntaxTreeNode(
          "MUL",
          [node, this.unary()],
          undefined,
          undefined,
          undefined
        )
      } else if (this.consume("/")) {
        node = new SyntaxTreeNode(
          "DIV",
          [node, this.unary()],
          undefined,
          undefined,
          undefined
        )
      } else {
        return node
      }
    }
  }

  /**
   * 単行演算子を含む
   */
  private unary(): SyntaxTreeNode {
    if (this.consume("-")) {
      return new SyntaxTreeNode(
        "SUB",
        [Parser.createNumberNode(0, undefined), this.primary()],
        undefined,
        undefined,
        undefined
      )
    }
    return this.primary()
  }

  private primary(): SyntaxTreeNode {
    if (this.isCurNumber()) {
      // 数値リテラル
      return Parser.createNumberNode(this.expectNumber(), undefined)
    }
    if (this.consume("(")) {
      // "(" expr ")"
      const node = this.add()
      this.expect(")")
      return node
    }
    const funcName = this.consumeFuncName()
    if (funcName !== undefined) {
      // 関数呼び出し
      this.expect("(")
      const args = this.args()
      this.expect(")")
      return new SyntaxTreeNode(
        "FUNC",
        args,
        undefined,
        funcName as ExcelFuncName,
        undefined
      )
    }
    // セルアドレス
    return this.cell()
  }

  private args(): SyntaxTreeNode[] {
    const res: SyntaxTreeNode[] = [this.add()]
    // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition, no-constant-condition
    while (true) {
      if (this.consume(",")) {
        res.push(this.add())
        continue
      }
      break
    }
    return res
  }

  private cell(): SyntaxTreeNode {
    const address = this.expectReserved()

    const parser = new Parser(address, this.getFormula)
    parser.init()

    const subTree = parser.expr()
    subTree.setAddress(address)

    return subTree
  }

  /**
   * Usage: Parserインスタンスを作成したら、最初にinit関数を実行する。
   */
  public init(): void {
    const formula = this.getFormula(this.rootAddress)
    const tokens = tokenizer(formula)
    this.tokens = tokens
  }

  public parse(): SyntaxTreeNode {
    return this.expr().setAddress(this.rootAddress)
  }
}

4. Reactアプリを作る

今回は特にパフォーマンスなどの制約はないため、公式ドキュメントの指示に従ってReactプロジェクトを立ち上げた。
少し触ったことがあったためフレームワークはNext.js、UIライブラリにはMaterialUIを用いている。

npx create-next-app@latest
npm install @mui/material @emotion/react @emotion/styled

また、jestのチュートリアルに従ってテスト環境のセットアップも行った。

React関連の実装に関してはただ書くだけなので深くは立ち入らないが、強いて言うなら以下のように関数コンポーネントを定義することで再帰的な描画を表現した。

const recTreeComponents = (
    node: SyntaxTreeNode,
    depth: number = 1
  ): React.JSX.Element => {
    const children = node.children.map((child) =>
      recTreeComponents(
        child,
        node.getAddress() !== undefined ? depth + 1 : depth
      )
    )
    if (node.getAddress() !== undefined) {
      const address = node.getAddress() as string
      return (
        <Paper key={node.id} elevation={depth} sx={{ p: 2 }}>
          <Stack spacing={2}>
            <Stack direction="row" alignItems="flex-end" spacing={8}>
              <TextField label="表示名" variant="standard" />
              <Typography>{node.getAddress()}</Typography>
              {node.getNodeType() === "LITERAL" ? (
                <TextField
                  label="値"
                  type="number"
                  variant="standard"
                  value={customValueMap.get(address) ?? node.getValue()}
                  onChange={(e) => {
                    const newValue = e.target.value
                    if (!isNumeric(newValue) && newValue !== "") {
                      // do nothing
                      return
                    }
                    const valueNum = newValue === "" ? 0 : Number(newValue)
                    setCustomValueMap((prev) => {
                      const newMap = new Map(prev)
                      newMap.set(address, valueNum)
                      return newMap
                    })
                  }}
                />
              ) : (
                <Typography>
                  計算結果:
                  {calcResultValueMap.get(address) ?? node.getCalculatedValue()}
                </Typography>
              )}
            </Stack>
            {children}
          </Stack>
        </Paper>
      )
    }

    if (children.length === 0 && children[0] !== undefined) {
      return children[0]
    }

    return <React.Fragment key={node.id}>{children}</React.Fragment>
  }

まとめ

元々は利便性のために実装しようと思っていたものですが、いざやってみるととても興味深いです。
コンパイラを作るようなことは前からやってみたいと思っていたので、この機会にできてよかったです。
最後まで読んでいただきありがとうございました。

参考文献

低レイヤを知りたい人のためのCコンパイラ作成入門