코드 자동 완성은 현대 IDE에서 프로그래밍 효율성을 높이는 핵심 기능입니다. 기존 방식은 접두어 기반 필터링과 정적 순위에 의존하지만, 알파벳 순의 긴 목록을 제시해 사용자에게 부담을 줍니다. 최근에는 LR 파싱 기반 방법이 제안되어 언어 문법을 바탕으로 후보를 생성하고, 오픈소스 프로그램 데이터를 활용해 순위를 계산하지만, 이는 구조적인 후보만 제시하며 실제 코드로의 수동 보완이 필요합니다. 이에 본 연구에서는 LR 파싱과 대형 언어 모델(LLM)을 결합한 하이브리드 방식을 제안합니다. 먼저 LR 파싱을 통해 구조적 후보를 생성한 뒤, LLM을 이용해 이를 실제 코드 형태로 보완하며, 오픈소스 데이터베이스의 순위 정보를 활용해 정밀도를 높입니다. 이를 통해 문법 기반 정확성과 생성 기반 유연성을 결합합니다. 우리는 LLM이 LR 구조적 후보로부터 실제 혜택을 얻는지 분석하고, 후보 없이 직접 생성한 결과와 비교하여 그 효과를 평가합니다. 또한 순위가 높은 구조적 후보를 활용할 때 LLM 기반 완성의 정확도가 얼마나 향상되는지도 탐구합니다. Microsoft Small Basic과 C 언어를 대상으로 한 VSCode 확장 기능을 통해 제안 방식을 실증하며, 이 시스템은 LR 문법이 정의된 모든 언어에 적용 가능한 범용적 솔루션입니다. 실험 결과, LR 파싱과 LLM 결합은 코드 완성의 정확성과 사용성을 모두 향상시키는 것으로 나타났습니다.
Code completion is a crucial feature in modern IDEs, improving programming efficiency. Traditional systems rely on prefix filtering and static ranking but often overwhelm users with lengthy, alphabetically sorted lists. Recent research has introduced LR-parsing-based approaches that derive completion candidates from language syntax and compute their ranks using open-source programs; however, these methods only suggest structural candidates, requiring manual refinement into complete code. To address this, we propose a hybrid method that integrates LR parsing with LLMs to enhance accuracy and usability. Our approach refines structural candidates using LR parsing into textual code suggestions via an LLM, referencing a database of ranked candidates from open-source programs. This combines the syntactic precision of LR parsing with the generative capabilities of LLMs. This study examines whether LLMs benefit from LR structural candidates in code completion. By comparing completions with and without these candidates, we assess their impact. Building on prior research, we also explore how leveraging top-ranked structural candidates can effectively enhance LLM-based code completion precision. We also demonstrate our method through VSCode extensions for Microsoft Small Basic and C. As a language-agnostic solution, our system applies to any language with a defined LR grammar. Our findings suggest that integrating LR parsing with LLM-based completion improves both accuracy and usability, paving the way for more effective code completion in modern IDEs.
이 논문은 LR 파서를 활용한 텍스트 기반 문법 완성(syntax completion) 기법을 제안한다. 우리는 문장의 형태(sentential forms)에 기반하여 자동완성할 텍스트 후보의 형식을 형식적으로 정의하고, LR 파싱 과정에서의 축소(reduction)를 이용해 이러한 후보를 계산하는 기본 알고리즘을 설계하였다. 이는 대부분의 기존 기법들이 후보의 정의를 비형식적으로 제공하는 것과 다르며, LR 파서를 사용하는 기존 문법 변환 기반 방식들과 달리 복잡한 변환 작업 없이도 사용이 가능하다는 점에서 차별된다. 제안된 방식은 LR 파서를 수정하지 않고 그대로 사용할 수 있으며, 추가적인 부담 없이 문법 완성 시스템을 구축할 수 있도록 한다. 실용적 적용을 위해, 우리는 정제된 후보 정의와 새로운 전략을 도입하여 기본 알고리즘을 확장하였다. 이 확장된 알고리즘은 기존 기법보다 현실적인 프로그래밍 언어 문법에 더 적합한 후보들을 계산할 수 있다. 구현은 Emacs 서버 상에서 이루어졌으며, Small Basic, C, Haskell 세 가지 실제 프로그래밍 언어로 평가하였다. 평가 결과, 전체 후보의 절반은 0.2초 이내에 계산되었고, 약 89.2%는 1초 이내에 계산되었으며, 나머지는 시간이 오래 걸렸다. 우리는 이러한 평가 결과를 논문에서 자세히 논의한다.
This paper presents a text-based syntax completion method that uses an LR parser. We propose formal definitions of candidate text to be completed based on the sentential forms. Moreover, we design basic algorithms for computing candidate texts through reductions in the LR parsing. This is unlike most existing methods, wherein the definition of candidates that are intended to be generated are given informally. In addition, this is unlike grammar transformation approaches that use LR parsers and is a currently burdensome task. The proposed method allows LR parsers to be adopted without modification and a syntax completion system to be built without incurring efforts. For practical purposes, we extended the basic algorithms using a new definition of refined candidates and a new strategy. The extended algorithms can compute more useful candidates for realistic programming language grammars than those of existing ones; Further, we implemented the algorithms on an Emacs server to demonstrate the feasibility of their application. We evaluated the extended algorithm with three real-world programming languages, Small Basic, C, and Haskell. The extended algorithm computes half of all candidates in less than or equal to 0.2 seconds and 89.2\% in approximately one second in the evaluation while computing the remaining candidates took a long time. We discuss its evaluation in detail.
(See Ranked Syntax Completion Using LR Parsing for the full paper.)
The polymorphic RPC calculus allows programmers to write succinct multitier programs using polymorphic location constructs. However, until now it lacked an implementation. We develop an experimental programming language based on the polymorphic RPC calculus. We introduce a polymorphic Client-Server (CS) calculus with the client and server parts separated. In contrast to existing untyped CS calculi, our calculus is not only able to resolve polymorphic locations statically, but it is also able to do so dynamically. We design a type-based slicing compilation of the polymorphic RPC calculus into this CS calculus, proving type and semantic correctness. We propose a method to erase types unnecessary for execution but retaining locations at runtime by translating the polymorphic CS calculus into an untyped CS calculus, proving semantic correctness.
본 논문은 LR 파서를 쉽게 개발하기 위하여 두 가지 아이디어를 제안한다. 첫째, 오토마타 생 성을 모듈화하여 새로운 프로그래밍 언어를 위한 파서 생성 도구를 쉽게 개발 할 수 있다. 둘째, 파서 명 세를 일반 프로그래밍언어로 작성하도록 구성하여 이 언어 개발 환경에서 제공하는 구문 오류, 자동 완성, 타입 오류 검사 기능들을 이용하여 파서 명세의 오류를 바로잡을 수 있다. 이 연구에서 제안한 아이디어 로 Python, Java, C++, Haskell로 파서를 작성할 수 있는 도구를 개발하였고, 실험을 통하여 위 두 가지 장점을 보였다.
This paper proposes two ways to develop LR parsers easily. First, one can write a parser specification in a general programming language and derive the benefits of syntax error checking, code completion, and type-error checking over the specification from the language’s development environment. Second, to make it easy to develop a parser tool for a new programming language, the automata generation for the parser specifications is in a modular form. With the idea proposed in this study, we developed a tool for writing parsers in Python, Java, C++, and Haskell. We also demonstrated the two aforementioned advantages in an experiment.
자체 수정 코드(Self-Modifying-Code)란 실행 시간 동안 스스로 실행 코드를 변경하는 코드를 말한다. 이런 기법은 특히 악성코드가 정적 분석을 우회하는 데 악용된다. 따라서 이러한 악성코드를 효과적으로 검출하려면 자체 수정 코드를 파악하는 것이 중요하다. 그동안 동적 분석 방법으로 자체 수정 코드를 분석해왔으나 이는 시간과 비용이 많이 든다. 만약 정적 분석으로 자체 수정 코드를 검출할 수 있다면 악성코드 분석에 큰 도움이 될 것이다. 본 논문에서는 LLVM IR로 변환한 바이너리 실행 프로그램을 대상으로 자체 수정 코드를 탐지하는 정적 분석방법을 제안하고, 자체 수정 코드 벤치마크를 만들어 이 방법을 적용했다. 본 논문의 실험 결과 벤치마크 프로그램을 컴파일로 변환한 최적화된 형태의 LLVM IR 프로그램에 대해서는 설계한 정적 분석 방법이 효과적이었다. 하지만 바이너리를 리프팅 변환한 비정형화된 LLVM IR 프로그램에 대해서는 자체 수정 코드를 검출하기 어려운 한계가 있었다. 이를 극복하기 위해 바이너리를 리프팅 하는 효과적인 방법이 필요하다.
Self-Modifying-Code is a code that changes the code by itself during execution time. This technique is particularly abused by malicious code to bypass static analysis. Therefor, in order to effectively detect such malicious codes, it is important to identify self-modifying-codes. In the meantime, Self-modify-codes have been analyzed using dynamic analysis methods, but this is time-consuming and costly. If static analysis can detect self-modifying-code it will be of great help to malicious code analysis. In this paper, we propose a static analysis method to detect self-modified code for binary executable programs converted to LLVM IR and apply this method by making a self-modifying-code benchmark. As a result of the experiment in this paper, the designed static analysis method was effective for the standardized LLVM IR program that was compiled and converted to the benchmark program. However, there was a limitation in that it was difficult to detect the self-modifying-code for the unstructured LLVM IR program in which the binary was lifted and transformed. To overcome this, we need an effective way to lift the binary code.