# 機能設計書 74-fsyacc

## 概要

本ドキュメントは、F#用のパーサージェネレータ「fsyacc」の設計を記述する。fsyaccは、文法仕様ファイル（.fsy）を読み込み、LALR(1)パーサーのF#ソースコードを生成するビルドツールである。

### 本機能の処理概要

**業務上の目的・背景**：コンパイラやインタプリタの実装において、構文解析（parsing）はトークン列を抽象構文木（AST）に変換する重要な処理段階である。fsyaccは、BNF形式の文法仕様からLALR(1)パーサーを自動生成することで、F#コンパイラ自身のパーサーや、F#を使用した言語処理系の開発を支援する。本ツールはocamlyaccやyaccに類似したツールであり、F#エコシステムにおける言語処理ツールチェーンの中核を担う。

**機能の利用シーン**：F#コンパイラのビルドプロセス中に、パーサー仕様ファイル（pars.fsy）からF#パーサーコード（pars.fs）を生成する際に使用される。また、F#で独自のプログラミング言語やDSLを開発する際にも利用可能である。

**主要な処理内容**：
1. コマンドライン引数の解析（出力ファイル名、モジュール名、ログ出力等）
2. 仕様ファイル（.fsy）の読み込みとパース
3. 文法のLALR(1)アイテム集合の構築
4. アクションテーブルとGOTOテーブルの計算
5. シフト/リデュース競合、リデュース/リデュース競合の検出と解決
6. F#パーサーコードの生成（.fs/.fsi）

**関連システム・外部連携**：FSharp.Text.Parsingライブラリと連携し、生成されたパーサーは実行時にこのライブラリの`Tables`型を使用する。また、fslexで生成されたレキサーと組み合わせて使用される。

**権限による制御**：本機能はビルドツールであり、ファイルシステムへの読み書きアクセス権限が必要。特別なユーザー権限制御は存在しない。

## 関連画面

本機能はコマンドラインツールであり、関連する画面は存在しない。

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | - |

## 機能種別

コード生成 / ビルドツール / LALR(1)パーサー生成

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| input | string | Yes | 入力仕様ファイルパス（.fsy） | ファイルが存在すること |
| -o | string | No | 出力ファイル名 | 有効なファイルパス |
| -v | flag | No | ログファイル出力 | - |
| --module | string | No | 生成モジュール名 | 有効なF#識別子 |
| --internal | flag | No | 内部モジュールとして生成 | - |
| --open | string | No | openするモジュール名（複数指定可） | 有効なモジュール名 |
| --lexlib | string | No | レキサーライブラリ名前空間 | デフォルト: FSharp.Text.Lexing |
| --parslib | string | No | パーサーライブラリ名前空間 | デフォルト: FSharp.Text.Parsing |
| --codepage | int | No | 入力ファイルのコードページ | 有効なコードページ番号 |
| --tokens | flag | No | トークン化のみ実行（デバッグ用） | - |
| --ml-compatibility | flag | No | OCaml Parsing互換モード | - |
| --buffer-type-argument | string | No | LexBuffer型引数 | デフォルト: 'cty |

### 入力データソース

- 仕様ファイル（.fsy）：文法ルールを定義したテキストファイル

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 出力ファイル | .fs | 生成されたF#パーサーソースコード |
| シグネチャファイル | .fsi | 生成されたF#シグネチャファイル |
| ログファイル | .fsyacc.output | パーサーテーブル詳細（-v指定時） |

### 出力先

- 指定された出力ファイルパス、またはデフォルトで入力ファイルと同じディレクトリに拡張子を.fsに変更したファイル

## 処理フロー

### 処理シーケンス

```
1. コマンドライン引数解析
   └─ ArgParser.Parseで各オプションを処理
2. 仕様ファイルの読み込み
   └─ readSpecFromFileで仕様をパース
3. LALR(1)テーブルのコンパイル
   └─ compileSpec→CompilerLalrParserSpec
4. テーブルサイズの表示
   └─ 状態数、非終端記号数、終端記号数、プロダクション数を出力
5. 出力ファイルの生成
   └─ writeSpecToFileで.fs/.fsiを生成
```

### フローチャート

```mermaid
flowchart TD
    A[開始: main] --> B[コマンドライン引数解析]
    B --> C{入力ファイル指定?}
    C -->|No| D[エラー: no input given]
    C -->|Yes| E[readSpecFromFile]
    E --> F{パース成功?}
    F -->|No| G[エラー出力・終了]
    F -->|Yes| H[compileSpec呼び出し]
    H --> I[ProcessParserSpecAst]
    I --> J[CompilerLalrParserSpec]
    J --> K[LALR1テーブル構築]
    K --> L{競合検出?}
    L -->|Yes| M[警告出力]
    L -->|No| N[テーブルサイズ表示]
    M --> N
    N --> O[writeSpecToFile]
    O --> P[.fs/.fsi生成]
    P --> Q[終了]
    D --> R[exit 1]
    G --> R
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-74-01 | 単一入力 | 入力ファイルは1つのみ指定可能 | 常時 |
| BR-74-02 | デフォルト出力 | 出力ファイル未指定時は入力ファイルの拡張子を.fsに変更 | -o未指定時 |
| BR-74-03 | 競合解決 | シフト/リデュース競合はシフトを優先 | 優先度未指定時 |
| BR-74-04 | 優先度指定 | %left/%right/%nonassocで演算子優先度を指定可能 | 常時 |
| BR-74-05 | 開始記号必須 | 少なくとも1つの%start宣言が必要 | 常時 |
| BR-74-06 | 型宣言必須 | 開始記号には%type宣言が必須 | 常時 |

### 計算ロジック

- **LALR(1)アルゴリズム**:
  - LR(0)カーネルの構築
  - Lookaheadの伝播と自発的生成の計算
  - アクションテーブル（Shift/Reduce/Accept/Error）の構築
  - GOTOテーブルの構築
- **アクションエンコーディング**:
  - Shift: 0x0000 | 状態番号
  - Reduce: 0x4000 | プロダクション番号
  - Error: 0x8000
  - Accept: 0xC000

## データベース操作仕様

本機能はデータベース操作を行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| FSY000 | 一般エラー | パースエラーまたは内部エラー | エラーメッセージを出力してexit 1 |
| - | 入力エラー | 入力ファイル未指定 | "no input given"を出力してexit 1 |
| - | 開始記号エラー | %start宣言がない | "at least one %start declaration is required" |
| - | 型宣言エラー | 開始記号に%typeがない | "a %type declaration is required for start token" |
| - | 重複宣言 | 同じ識別子に複数の宣言 | 重複を報告 |

### リトライ仕様

リトライは行わない。エラー発生時は即座にexit 1で終了。

## トランザクション仕様

本機能はトランザクション管理を必要としない。

## パフォーマンス要件

- 大規模な文法仕様でも実用的な時間内にテーブル生成を完了すること
- F#コンパイラの文法（数百のプロダクション）を処理可能

## セキュリティ考慮事項

- 入力ファイルの信頼性に依存
- 生成されたコードは直接実行されるため、仕様ファイルの出所を確認すること

## 備考

- F#コンパイラ自身のパーサー（pars.fsy→pars.fs）の生成にも使用される
- シフト/リデュース競合、リデュース/リデュース競合の数がコンソールに報告される

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | fsyaccast.fs | `buildtools/fsyacc/fsyaccast.fs` | AST定義、Action型、テーブル型 |

**主要処理フロー**:
- **16-26行目**: ParserSpec型 - 入力仕様のAST
- **29-31行目**: Symbol型 - Terminal/NonTerminal
- **62行目**: Production型 - プロダクション定義
- **143-148行目**: Action型 - Shift/Reduce/Accept/Error
- **348-358行目**: CompiledSpec型 - コンパイル結果

**読解のコツ**: `Item0`型はプロダクションインデックスとドット位置をuint32にエンコードした型。上位16ビットがプロダクションインデックス、下位16ビットがドット位置。

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | fsyacc.fs | `buildtools/fsyacc/fsyacc.fs` | メイン関数とコマンドライン処理 |

**主要処理フロー**:
- **13-25行目**: グローバル変数定義（オプション値）
- **27-40行目**: usage - コマンドライン引数定義
- **44-84行目**: main関数 - 全体フロー制御
- **58行目**: compileSpec呼び出し

#### Step 3: LALR(1)コンパイルを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | fsyaccast.fs | `buildtools/fsyacc/fsyaccast.fs` | CompilerLalrParserSpec関数 |

**主要処理フロー**:
- **361-919行目**: CompilerLalrParserSpec - LALR(1)テーブル構築
- **386-431行目**: FIRST集合の計算
- **543-562行目**: LR(0)クロージャ計算
- **581-597行目**: LR(0)カーネル構築
- **630-644行目**: LALR(1)クロージャ計算
- **664-701行目**: 自発的生成と伝播の計算
- **732-888行目**: アクションテーブル構築

#### Step 4: コード生成を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | fsyaccdriver.fs | `buildtools/fsyacc/fsyaccdriver.fs` | writeSpecToFile |

**主要処理フロー**:
- **136-145行目**: actionCoding - アクションのエンコーディング
- **179-548行目**: writeSpecToFile - ファイル出力

### プログラム呼び出し階層図

```
fsyacc.main
    │
    ├─ ArgParser.Parse
    │      └─ usage定義を使用して引数解析
    │
    ├─ readSpecFromFile
    │      ├─ UnicodeFileAsLexbuf
    │      └─ Parser.spec / Lexer.token
    │
    ├─ compileSpec
    │      ├─ ProcessParserSpecAst
    │      │      └─ 優先度情報の処理
    │      │
    │      └─ CompilerLalrParserSpec
    │             ├─ FIRST集合計算
    │             ├─ LR(0)カーネル構築
    │             ├─ Lookahead計算（自発的/伝播）
    │             ├─ アクションテーブル構築
    │             │      └─ 競合解決
    │             └─ GOTOテーブル構築
    │
    └─ writeSpecToFile
           ├─ token型定義出力
           ├─ tokenId型定義出力
           ├─ テーブル配列出力
           │      ├─ _fsyacc_gotos
           │      ├─ _fsyacc_actionTableElements
           │      └─ _fsyacc_reductions
           └─ パーサー関数出力
```

### データフロー図

```
[入力]                    [処理]                              [出力]

.fsy仕様ファイル ───────▶ Parser.spec ──────────────────────▶ ParserSpec (AST)
                               │
                               ▼
                         ProcessParserSpecAst
                               │
                               ▼
                         ProcessedParserSpec
                               │
                               ▼
                         CompilerLalrParserSpec
                               │
                               ▼
                         CompiledSpec
                               │
                               ▼
                         writeSpecToFile
                               │
                               ├───────────────────────────────▶ .fs ファイル
                               │
                               ├───────────────────────────────▶ .fsi ファイル
                               │
                               └───────────────────────────────▶ .fsyacc.output（-v時）
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| fsyacc.fs | `buildtools/fsyacc/fsyacc.fs` | ソース | メインエントリーポイント |
| fsyaccast.fs | `buildtools/fsyacc/fsyaccast.fs` | ソース | AST定義とLALR(1)コンパイラ |
| fsyaccdriver.fs | `buildtools/fsyacc/fsyaccdriver.fs` | ソース | コード生成とファイル出力 |
| fsyacclex.fs | `buildtools/fsyacc/fsyacclex.fs` | ソース | 仕様ファイルのレキサー |
| fsyaccpars.fs | `buildtools/fsyacc/fsyaccpars.fs` | ソース | 仕様ファイルのパーサー |
| Arg.fs | `buildtools/fsyacc/Arg.fs` | ソース | コマンドライン引数解析 |
| Lexing.fs | `buildtools/fsyacc/Lexing.fs` | ソース | レキシングユーティリティ |
| Parsing.fs | `buildtools/fsyacc/Parsing.fs` | ソース | パーシングユーティリティ |
