Ranked Syntax Completion

with LR Parsing

ACM SAC 2024 (SE Track)

April 11, 2024

Kwanghoon Choi

Chonnam National University, Korea

Sooyeon Hwang

Chonnam National University, Korea

Hyeon-Ah Moon

Sogang University, Korea

Isao Sasano

Shibaura Institute of Technology, Japan

Introduction

The feature of syntax completion in IDEs

• offers suggestions for completing code segments right after a certain code that a programmer writes
• uses the current context and syntax rules of the programming language

​

The importance of syntax completion for efficient programming:

• Learning aid, early detection of syntax errors, and boosts productivity

​

2

Examples: Identifier Completion in Microsoft SmallBasic

3

cf. Identifier Completion for C11 in Microsoft Visual Studio

Motivation and Challenges

The limitations of existing syntax completion methods

• Mostly identifier completions, overwhelming choices, static suggestions

​

The need for a ranked list of syntax structure candidates

• Addressing more complex expressions than identifiers
• Adjusting the order of the list for efficient syntax completion

4

Our System: Ranked Syntax Structure Completion for SmallBasic

Suggest syntax structure candidates sorted by preinvestigated frequencies

5

Our System: Ranked Syntax Structure Completion for C11

A language-parametric feature given only a parser written in LR grammar

6

Contributions

The text-based ranked syntax completion method with LR parsing

• Design of LR parsing-based algorithms to systematically collect and rank syntax completion candidates
• Implementation of a language-parametric tool for any language defined by LR grammars
• Evaluation with SmallBasic and C11 introductory programming to highlight the importance of the ranked candidates

7

Overview

Two-phase approach: Collecting&ranking phase and Query phase

​

​

​

​

Highlight: The use of LR parsing in the system

- It enables a precise analysis based on the programming language’s syntax rules

8

Collecting&ranking phase (offline)

Query phase (online)

Collection and Ranking Phase (1/3)

How candidates are collected and ranked from sample programs?

- Input sample program: TextWindow.WriteLine(“Hello World”)

​

​

​

​

- Expected outcome:

​

9

Collection and Ranking Phase (2/3)

Mapping the cursor positions to a set of parse states

10

A reduce action replaces top stack symbols with the lhs nonterminal of a production rule whose rhs matches the top stack symbols.

A shift action takes the next token symbol from the token list and stacks it.

Collection and Ranking Phase (3/3)

For each parse state, collect candidates on reduce actions crossing the corresponding cursor position, and and count the # of the occurrences

11

An evidence for the candidate at S30

Collection and Ranking Phase (3/3) (cont.)

Specifications of simple candidates: Suffix sentential forms

• The concept of suffix sentential form intuitively represents the remaining portion of the program text entered up to the current position [18,19].

12

ExprStatement -> ID. ID ( Exprs )

TextWindow . WriteLine ( “Hello World” )

α

γ

ID . ID ( EXPR )

Collecting a completion here

(Cursor position 3, i.e. S30)

An evidence for the candidate at S30

Query Phase

How the system retrieves syntax completion suggestions for the user

13

Online LR parsing from the beginning of a program to the cursor position to determine parse states

Getting candidates and ranks for the parse states from the offline database

+

Two Algorithms

Alg. 1 Collecting and ranking candidates for parse states over a sample program

• For each token, parse the program text up to the token to get a parse state, and continue to parse until a reduce action satisfying the specification
• Collect a pair of the parse state with the symbols accumulated during the continuation of the parse

Alg. 2 Computing a set of parse states for the current cursor position on editing

• Parse the program text up to the cursor position to get a parse state, and
• Union all states reachable by zero or more reduce actions from it

14

(See the details of the algorithms in the paper.)

Implementation

An extension of YAPB, a language-agnostic LR parser builder [9], with the proposed feature of syntax completion

15

LR grammar

YAPB

(with the extension of the two algs.)

LR parser

Syntax

completion

engine

Syntax completion engine

= a candidate collector + a parse state converter

Implementation

For evaluation, the implementation of two parsers for SmallBasic and C11 using the extended YAPB

16

Demo

MySmallBasic, a SmallBasic environment for coding education, with a support of syntax completion suggestions using the extended YAPB

- Converting temperatures from Fahrenheit to Celsius

17

18

Evaluation Methodology

The datasets used for candidate collection:,

• Smallbasic community programs: 3,701 programs encompassing nearly 789,023 lines of code
• C11 open-source projects(cJSON, lcc, bc, gzip, screen, make, tar): 412 programs, totaling approximately 308,599 lines of code

​

Accuracy of suggestions

• How often the top suggestion was what the programmer expects

19

Evaluation Results: SmallBasic

The datasets used for testing:

• Microsoft SmallBasic tutorial: 27 programs spanning 155 lines of code

​

Results on the effectiveness of ranked syntax completion in SmallBasic

​

20

Average: 0.8 times

Pressing the down key fewer times leads to finding the desired candidate faster.

Evaluation Results: C11

The datasets used for testing:

• The Kernighan and Ritchie’s book on the C programming language: 106 exercise programs totaling 11,218 lines of code

Results on the effectiveness of ranked syntax completion in C11

​

21

Average: 2.15 times

Pressing the down key fewer times leads to finding the desired candidate faster.

Related work

Ranking candidates for identifier completion

• Using program editing history [15]
• Subsequence matching rather than prefix matching [5]
• Project-specific candidate [6]
• Synthesizing method calls by calculating potential token sequences [13]
• IntelliCode Compose leveraging GPT-C [21]

22

Related work

Parser-based code completion

• Identifier completion using the LL(k) parser generator ANTLR [22]
• A substring parser based on GLR parsing as code completion [14]
• A LALR(1) parser based code completion [19]

​

​

23

Future directions

How to flesh out the structural candidates by

• Combination of identifier completion with syntax structural completion
• Transformation of syntax structure candidates into snippets supporting programmer’s writing
• The use of Large Language Models (LLMs) guided by syntax structure candidates

24

Future directions

Parsing the syntactically erroneous prefix of programs

- Error recovery

​

Efficient calculation of parse states for the given cursor positions

- Incremental parsing

​

=> A possible approach is to use the open-source software, tree-sitter, for incremental parsing with the error recovery support

25

Conclusions

A new approach to syntax complexion that leverages LR parsing for collecting and ranking syntax completion candidates

• A language-parametric tool with its feasibility evaluation
• Education benefits by guiding users towards the correct use of syntax

26

27

28

Discussion

Key contributions of this paper

• The development of the two algorithms utilizing LR parsing to systematically collect and suggest ranked syntax completion candidates
• The language-parametric tool capable of providing ranked syntax completion for any language defined by an LR grammar
• The importance of ranking data
• Refinement of completion suggestions
• A data-driven approach to syntax completion, allowing for continuous refinement of suggestions based on actual usage patterns
• Ranked suggestions can server as an educational tool

29

Collection and Ranking Phase

At the cursor position (2), the user has input “TextWindow”, i.e., ID.

The anticipated subsequent input from the user is “. WriteLine ( “Hello World” ).

The completion suggestion should be “. ID ( Exprs )” from the two items 7 and 8:

30

[State S6]

Future directions

Complex form of structural candidates, for example, various examples involving function pointers in C11:

• int (*f)(int,int) ;
• int performOperation(int (*operation)(int, int), int x, int y) { … }
• int (*selectOperation(char op))(int, int) { … }

31

=> type_specifier_nonunique ( * var_name ) ( parameter_type_list )

=> type_specifier_nonunique ( * var_name ( type_specifier_nonunique var_name ) ) ( parameter_list )